Length-nonincreasing rewriting system

From Groupprops

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.