Thue systems and the Church-Rosser property: replacement systems, specification of formal languages, and presentations of monoids. (English) Zbl 0563.68062

Combinatorics on words. Progress and perspectives, Proc. Int. Meet., Waterloo/Can. 1982, 1-38 (1983).
[For the entire collection see Zbl 0552.00014.]
The paper surveys the properties of and decidability results about finite and infinite Thue systems that are Church-Rosser. Two sections of the paper are dedicated to interrelationships between monadic finite Thue systems that are Church-Rosser and specifications of formal languages, and between finite Thue systems that are Church-Rosser and presentations of monoids.
Reviewer: D.Lucanu


68Q45 Formal languages and automata
03D03 Thue and Post systems, etc.
20M35 Semigroups in automata theory, linguistics, etc.


Zbl 0552.00014