Shortlex-reducing rewriting system

From Groupprops

Template:Rewriting system property

Definition

A rewriting system is said to be shortlex-reducing if the following is true: there is a total ordering on the elements of the underlying alphabet such that for every rewrite, the right side is less than the left side, in the shortlex ordering on the set of words with respect to that total ordering.

Relation with other properties

Stronger properties

Weaker properties

Metaproperties

Free product-closedness

This property of a rewriting system is free product-closed. In other words, if we have two rewriting systems satisfying the property, the natural free product of these rewriting systems also satisfies the property

The rewriting system corresponding naturally to a free product of shortlex-reducing rewriting systems, is also shortlex-reducing. We can impose any total ordering on the new alphabet that, restricted to the alphabet of each factor, gives the total ordering on that factor.