Confluent and Other Types of Thue Systems
Ronald V. Book · Journal of the ACM · 1982
Confluent and other types of finite Thue systems are studied.Sufficlem condmons are developed for every congruence class and every fimte union of congruence classes defined by such a system to be a determtmsttc context-free language.It is shown that the word problem for Church-Rosser systems is decidable m hnear t~me Categories and Subject Descriptors F 4 2 [Mathematical Logic and Formal Languages] Grammars and Other Rewriting Systems--Thue systems, F 4 3 [Mathematical Logic and Formal Languages]: Formal Languages--deczswn problems