Thumbnail
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

   Open content in new tab
Source: ACM Digital Library