×

zbMATH — the first resource for mathematics

Some remarks on presentations by finite Church-Rosser Thue systems. (English) Zbl 0636.20023
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