Drunken man infinite words complexity
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 599-613
Cet article a éte moissonné depuis la source Numdam
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 when goes to infinity.
@article{ITA_2008__42_3_599_0,
author = {Gonidec, Marion Le},
title = {Drunken man infinite words complexity},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {599--613},
year = {2008},
publisher = {EDP-Sciences},
volume = {42},
number = {3},
doi = {10.1051/ita:2008012},
mrnumber = {2434037},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2008012/}
}
TY - JOUR AU - Gonidec, Marion Le TI - Drunken man infinite words complexity JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2008 SP - 599 EP - 613 VL - 42 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2008012/ DO - 10.1051/ita:2008012 LA - en ID - ITA_2008__42_3_599_0 ER -
%0 Journal Article %A Gonidec, Marion Le %T Drunken man infinite words complexity %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 599-613 %V 42 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2008012/ %R 10.1051/ita:2008012 %G en %F ITA_2008__42_3_599_0
Gonidec, Marion Le. Drunken man infinite words complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 599-613. doi: 10.1051/ita:2008012
Cité par Sources :