Drunken man infinite words complexity
Marion Le Gonidec (2008)
RAIRO - Theoretical Informatics and Applications
Similarity:
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 (log ) when goes to infinity.