Homogeneous Thue systems and the Church-Rosser property

✍ Scribed by Ronald V Book

• Publisher: Elsevier Science
• Year: 1984
• Tongue: English
• Weight: 455 KB
• Volume: 48
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(84)90177-8

✦ Synopsis

Homogeneous Thue systems are considered. It is shown that if a homogeneous Thue system is not Church-Rosser, then there is no Chttrch-Rosser system that is equivalent to it. This result contrasts with the theorems of 0'Dfnlaing [10,11] showing that it is undecidable whether the congruence generated by a finite Thue system is also generated by a finite Church-Rosser system.