### Testing for the Church-Rosser PropertyTesting for the Church-Rosser Property

Access Restriction
Subscribed

 Author Sethi, Ravi Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1974 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $(\textit{S},$ ⇒, ≡), where $\textit{S}$ is a set of objects, ⇒ is a transformation, and ≡ is an equivalence relation on $\textit{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 $(\textit{S},$ ⇒, ≡) is Church-Rosser using information about parts of the system, i.e. considering cases where ⇒ is ⇒1 ∪ ⇒2, or ≡ is (≡1 ∪ ≡2)*. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1974-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 21 Issue Number 4 Page Count 9 Starting Page 671 Ending Page 679

#### Open content in new tab

Source: ACM Digital Library