×

Bornes inférieures sur la complexité des facteurs des mots infinis engendrés par morphismes itérés. (French) Zbl 0543.68061

Theoretical aspects of computer science, Symp., Paris 1984, Lect. Notes Comput. Sci. 166, 230-240 (1984).
Résumé: [For the entire collection see Zbl 0533.00025.]
A. Ehrenfeucht, K. P. Lee et G. Rozenberg [Theor. Comput. Sci. 1, 59-75 (1975; Zbl 0316.68043)] ont montré que la complexité des facteurs des DOL langages (et donc des mots infinis engendrés par morphismes itérés) était majorée par \(cn^ 2\) (resp. cn log n, cn) suivant que le morphisme est quelconque, croissant ou uniforme. Nous introduisons une classe intermédiaire dont la complexité est majorée par cn log log n. De plus nous montrons que tout mot infini engendré par morphisme a une complexité en \(O(n^ 2)\), O(n log n), O(n log log n), O(n) ou O(1) suivant la nature du morphisme.

MSC:

68Q45 Formal languages and automata