Length-reducing rewriting system
Template:Rewriting system property
This article is about a standard (though not very rudimentary) definition in an area related to, but not strictly part of, group theory
Definition
A rewriting system is said to be length-reducing if for every rewrite, the length of the word on the right is strictly less than the length of the word on the left.
Note that while this term makes sense for a general rewriting system of any monoid, it can also be made sense of in the context of rewriting system for a group.
Relation with other properties
Stronger properties
Some stronger properties of rewriting systems are:
Weaker properties
Metaproperties
Local testability
This property of a rewriting system is locally testable, in other words, it can be reduced to testing a particular property for each rewrite in the system
To check whether a rewriting system is length-reducing, we simply need to check, for every rewrite, whether that is length-reducing. That is, the property is simply a certain property being true for each rewrite.
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
That a free product of length-reducing rewriting systems is length-reducing follows from its being locally testable.