Drunken man infinite words complexity

Marion Le Gonidec

RAIRO - Theoretical Informatics and Applications (2008)

  • Volume: 42, Issue: 3, page 599-613
  • ISSN: 0988-3754

Abstract

top
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.


How to cite

top

Le 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
  1. J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. Simon Stevin1 (1994) 133–143.  
  2. J.-P. Allouche and J. Shallit, Automatic sequences. Theory, applications, generalizations. Cambridge University Press (2003).  
  3. J. Cassaigne, Special factors of sequences with linear subword complexity. In Developments in language theory (Magdeburg, 1995), World Sci. Publishing (1996) 25–34.  
  4. J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.  
  5. A. Cobham, Uniform-tag sequences. Math. Syst. Theory6 (1972) 164–192.  
  6. S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.  
  7. S. Ferenczi, Substitution dynamical systems on infinite alphabets. Ann. Inst. Fourier56 (2006) 2315–2343.  
  8. E. Fouvry and C. Mauduit, Sur les entiers dont la somme des chiffres est moyenne. J. Number Theory114 (2005) 135–152.  
  9. P. Kůrka, Topological and symbolic dynamics, Cours spécialisés Vol. 11, SMF (2003).  
  10. M. Le Gonidec, Sur la complexité de mots infinis engendrés par des q-automates dénombrables. Ann. Inst. Fourier56 (2006) 2463–2491.  
  11. M. Le Gonidec, Sur la complexité des mots q∞-automatiques. Ph.D. thesis, Université Aix-Marseille II (2006).  
  12. C. Mauduit, Propriétés arithmétiques des substitutions et automates infinis. Ann. Inst. Fourier56 (2006) 2525–2549.  
  13. 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.  
  14. 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).  
  15. L. Staiger, Kolmogorov complexity of infinite words. CDMTCS Research Report Series279 (2006).  

NotesEmbed ?

top

You must be logged in to post comments.