Infinite regular Thue systems
A `regular' Thue system is a length-reducing Thue system
for which the set of right=hand-sides
of rules is finite and for each right-hand-side the set of corresponding
left-hand-sides is regular. It generalises ordinary (finite) Thue systems.
The following are shown. Let S be a regular Thue system.
(i) If it is Church-Rosser, then its word problem is decidable in linear
time. (ii) If it is monadic and Church-Rosser, it defines a nontrivial
boolean algebra of deterministic context-free languages.
(iii) Equivalence of regular monadic Church-Rosser systems is decidable.
(iv) The Church-Rosser property is decidable for regular monadic systems.
(v) The Church-Rosser property is undecidable for general
regular systems.