An almost-confluent congruential language which is not Church-Rosser congruential

作者：Dunlaing Colm O^*

来源：Theoretical Computer Science, 2015, 589: 141-146.

DOI：10.1016/j.tcs.2015.04.018

• Thue systems
• String-rewriting systems
• Congruence
• Congruential language

It is fairly easy to show that every regular set is an almost-confluent congruential language (ACCL), and it is known [3] that every regular set is a Church-Rosser congruential language (CRCL). Whether there exists an ACCL, which is not a CRCL, seems to remain an open question. In this note we present one such ACCL.

• 出版日期2015-7-19