On rich words. (English) Zbl 0563.03022

Combinatorics on words. Progress and perspectives, Proc. Int. Meet., Waterloo/Can. 1982, 39-61 (1983).
[For the entire collection see Zbl 0552.00014.]
A Z-word is a mapping from the integers Z to a finite alphabet A, i.e. to a finite set of symbols. Thus a Z-word is a two-way infinite word. Such a word is said to be rich (or random) if every finite word occurs as a block infinitely often to both, negative and positive, directions. The author shows that the monadic second order theory of rich words is complete. This improves a result by V. Benda [Infinite words as universes; unpublished] who showed the completeness of the first order theory of rich words. The infinite behaviour of finite automata as well as Fraisse-Ehrenfeucht games come into use in the proof.
Reviewer: T.Harju


03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.


Zbl 0552.00014