Complexité des facteurs des mots infinis engendrés par morphismes itérés. (French) Zbl 0554.68053

Pansiot, Jean-Jacques

Automata, languages and programming, 11th Collog., Antwerp/Belg. 1984, Lect. Notes Comput. Sci. 172, 380-389 (1984).

Summary: [For the entire collection see Zbl 0543.00014.]
A. Ehrenfeucht, K. P. Lee and G. Rozenberg [Theor. Comput. Sci. 1, 59–75 (1975; Zbl 0316.68043)] have shown that the subword complexity of DOL languages (hence for infinite words obtained by iterated morphisms) is bounded by \(cn^ 2\) (resp. \(cn\log n\), \(cn\)) if the morphism is arbitrary (resp. growing, uniform). We introduce a new class with complexity bounded by \(cn \log \log n\). Moreover, we show that every infinite word generated by morphism has a complexity in \(O(n^ 2)\), \(O(n \log n)\), \(O(n\log\log n)\), \(O(n)\) or \(O(1)\) according to the type of the morphism.

MSC:

68Q45

Formal languages and automata

Keywords:

subword complexity of DOL languages; infinite words; iterated morphisms

Citations:

Zbl 0543.00014; Zbl 0316.68043