Article contents
Drunken man infinite words complexity
Published online by Cambridge University Press: 03 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(log2n)2 when n goes to infinity.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 3: JM'06 , July 2008 , pp. 599 - 613
- Copyright
- © EDP Sciences, 2008
References
- 4
- Cited by