Testing for the Church-Rosser Property

Abstract

The central notion in a replacement system is one of a transformation on a set of objects. Starting with a given object, in one “move” it is possible to reach one of a set of objects. An object from which no move is possible is called irreducible. A replacement system is Church-Rosser if starting with any object a unique irreducible object is reached. A generalization of the above notion is a replacement system ( S , ⇒, ≡), where S is a set of objects, ⇒ is a transformation, and ≡ is an equivalence relation on S . A replacement system is Church-Rosser if starting with objects equivalent under ≡, equivalent irreducible objects are reached. Necessary and sufficient conditions are determined that simplify the task of testing if a replacement system is Church-Rosser. Attention will be paid to showing that a replacement system ( S , ⇒, ≡) is Church-Rosser using information about parts of the system, i.e. considering cases where ⇒ is ⇒ ₁ ∪ ⇒ ₂ , or ≡ is (≡ ₁ ∪ ≡ ₂ ) ^* .