Length-nonincreasing rewriting system
Template:Rewriting system property
Definition
A rewriting system is said to be length-nonincreasing if for every rewrite in it, the length on the right side is not more than the length on the left side.
Though this property is studied for a rewriting system for any monoid, it is of particular interest in the case of a rewriting system for a group. Since the free group rewrites are in any case length-nonincreasing, we only need to look at the other rewrites.
Relation with other properties
Stronger 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
The property of being length-nonincreasing is basically a certain property being satisfied for each rewrite separately.