Testing for the Church-Rosser Property

Ravi Sethi

Research output: Contribution to journalArticlepeer-review

43 Scopus citations


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 ⇒1 ∪ ⇒2, or ≡ is (≡1 ∪ ≡2)*.

Original languageEnglish (US)
Pages (from-to)671-679
Number of pages9
JournalJournal of the ACM (JACM)
Issue number4
StatePublished - Oct 1 1974


  • Church-Rosser systems
  • combinatorial theories

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Testing for the Church-Rosser Property'. Together they form a unique fingerprint.

Cite this