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

Book, Ronald V.

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

MSC:

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

Keywords:

decidability; Thue systems; specifications of formal languages; presentations of monoids