Geodesic
Drunken man infinite words complexity
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 599-613

Voir la notice de l'article provenant de la source Numdam

MR

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.

DOI : 10.1051/ita:2008012
Classification : 11B85, 68R15 
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
@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

Cité par Sources :