Drunken man infinite words complexity
RAIRO - Theoretical Informatics and Applications (2008)
- Volume: 42, Issue: 3, page 599-613
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topLe Gonidec, Marion. "Drunken man infinite words complexity." RAIRO - Theoretical Informatics and Applications 42.3 (2008): 599-613. <http://eudml.org/doc/250354>.
@article{LeGonidec2008,
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.
},
author = {Le Gonidec, Marion},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {block-complexity; infinite words generated by countable automata; morphisms on countable alphabets; block-complexity},
language = {eng},
month = {6},
number = {3},
pages = {599-613},
publisher = {EDP Sciences},
title = {Drunken man infinite words complexity},
url = {http://eudml.org/doc/250354},
volume = {42},
year = {2008},
}
TY - JOUR
AU - Le Gonidec, Marion
TI - Drunken man infinite words complexity
JO - RAIRO - Theoretical Informatics and Applications
DA - 2008/6//
PB - EDP Sciences
VL - 42
IS - 3
SP - 599
EP - 613
AB - 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.
LA - eng
KW - block-complexity; infinite words generated by countable automata; morphisms on countable alphabets; block-complexity
UR - http://eudml.org/doc/250354
ER -
References
top- J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. Simon Stevin1 (1994) 133–143.
- J.-P. Allouche and J. Shallit, Automatic sequences. Theory, applications, generalizations. Cambridge University Press (2003).
- J. Cassaigne, Special factors of sequences with linear subword complexity. In Developments in language theory (Magdeburg, 1995), World Sci. Publishing (1996) 25–34.
- J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.
- A. Cobham, Uniform-tag sequences. Math. Syst. Theory6 (1972) 164–192.
- S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.
- S. Ferenczi, Substitution dynamical systems on infinite alphabets. Ann. Inst. Fourier56 (2006) 2315–2343.
- E. Fouvry and C. Mauduit, Sur les entiers dont la somme des chiffres est moyenne. J. Number Theory114 (2005) 135–152.
- P. Kůrka, Topological and symbolic dynamics, Cours spécialisés Vol. 11, SMF (2003).
- M. Le Gonidec, Sur la complexité de mots infinis engendrés par des q-automates dénombrables. Ann. Inst. Fourier56 (2006) 2463–2491.
- M. Le Gonidec, Sur la complexité des mots q∞-automatiques. Ph.D. thesis, Université Aix-Marseille II (2006).
- C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis. Ann. Inst. Fourier56 (2006) 2525–2549.
- C. Mauduit and A. Sárközy, On the arithmetic structure of sets characterized by sum of digits properties. J. Number Theory61 (1996) 25–38.
- J.-J. Pansiot, Complexité des facteurs des mots infinis engendrés par morphismes itérés. Lecture Notes Comput. Sci.172 (1985) 380–389. Automata, languages and programming (Antwerp, 1984).
- L. Staiger, Kolmogorov complexity of infinite words. CDMTCS Research Report Series279 (2006).
Citations in EuDML Documents
topNotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.