Shortlex-reducing rewriting system
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.