RAIRO - Theoretical Informatics and Applications (RAIRO: ITA)

| Abstract | PDF (222.4 KB) | References |

RAIRO-Theor. Inf. Appl. 42, 599-613 (2008)
DOI: 10.1051/ita:2008012

Drunken man infinite words complexity

Marion Le Gonidec

Institut de Mathématiques, Université de Liège, Grande traverse 12 B.37, 4000 Liège, Belgium; M.LeGonidec@ulg.ac.be

Published online: 3 June 2008

Abstract
In this article, we study the complexity of drunken man infinite words. We show that these infinite words, generated by a deterministic and complete countable automaton, or equivalently generated by a substitution over a countable alphabet of constant length, have complexity functions equivalent to $n(\log_2 n)^2$ when n goes to infinity.