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).  Zbl1086.11015
  3. J. Cassaigne, Special factors of sequences with linear subword complexity. In Developments in language theory (Magdeburg, 1995), World Sci. Publishing (1996) 25–34.  Zbl1096.68690
  4. J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.  Zbl0921.68065
  5. A. Cobham, Uniform-tag sequences. Math. Syst. Theory6 (1972) 164–192.  Zbl0253.02029
  6. S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.  Zbl0936.37008
  7. S. Ferenczi, Substitution dynamical systems on infinite alphabets. Ann. Inst. Fourier56 (2006) 2315–2343.  Zbl1147.37007
  8. E. Fouvry and C. Mauduit, Sur les entiers dont la somme des chiffres est moyenne. J. Number Theory114 (2005) 135–152.  Zbl1084.11045
  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.  Zbl1121.68090
  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.  Zbl1147.11016
  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).  Zbl0554.68053
  15. L. Staiger, Kolmogorov complexity of infinite words. CDMTCS Research Report Series279 (2006).  Zbl1124.68050

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.