Some remarks on presentations by finite Church-Rosser Thue systems. (English) Zbl 0636.20023

Diekert, Volker

STACS 87, Theoretical aspects of computer science, Proc. 4th annu. Symp., Passau/FRG 1987, Lect. Notes Comput. Sci. 247, 272-285 (1987).

[For the entire collection see Zbl 0604.00016.]
An infinite cancellative monoid where the classes of the syntactical congruence of its center form a finite group has no presentation by a finite Church-Rosser Thue System unless the monoid is isomorphic to \({\mathbb{Z}}\) or \({\mathbb{N}}\). This generalizes a result of J. Avenhaus, R. Book and C. Squier [RAIRO, Inf. Théor. 18, 47-52 (1984; Zbl 0542.20038)] on commutative monoids.
An infinite group with an abelian subgroup of finite index admits a finite Church-Rosser Thue presentation if and only if the group is isomorphic to \({\mathbb{Z}}\) or isomorphic to the free product \({\mathbb{Z}}/2{\mathbb{Z}}*{\mathbb{Z}}/2{\mathbb{Z}}\). A group having a finite Church- Rosser Thue presentation is proved to be context-free.

MSC:

20F05	Generators, relations, and presentations of groups
20M05	Free semigroups, generators and relations, word problems
20M35	Semigroups in automata theory, linguistics, etc.
68Q45	Formal languages and automata

Keywords:

infinite cancellative monoid; syntactical congruence; finite Church- Rosser Thue System; infinite group; abelian subgroup of finite index; finite Church-Rosser Thue presentation; free product