Drunken man infinite words complexity
Institut de Mathématiques, Université de Liège, Grande traverse 12 B.37, 4000 Liège, Belgium; M.LeGonidec@ulg.ac.be
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(log2n)2 when n goes to infinity.
Mathematics Subject Classification: 11B85 / 68R15
© EDP Sciences, 2008