Three complexity functions

Sébastien Ferenczi; Pascal Hubert

RAIRO - Theoretical Informatics and Applications (2012)

  • Volume: 46, Issue: 1, page 67-76
  • ISSN: 0988-3754

Abstract

top
For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.

How to cite

top

Ferenczi, Sébastien, and Hubert, Pascal. "Three complexity functions." RAIRO - Theoretical Informatics and Applications 46.1 (2012): 67-76. <http://eudml.org/doc/277834>.

@article{Ferenczi2012,
abstract = {For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes. },
author = {Ferenczi, Sébastien, Hubert, Pascal},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Infinite words; symbolic dynamical systems; complexity; infinite words},
language = {eng},
month = {3},
number = {1},
pages = {67-76},
publisher = {EDP Sciences},
title = {Three complexity functions},
url = {http://eudml.org/doc/277834},
volume = {46},
year = {2012},
}

TY - JOUR
AU - Ferenczi, Sébastien
AU - Hubert, Pascal
TI - Three complexity functions
JO - RAIRO - Theoretical Informatics and Applications
DA - 2012/3//
PB - EDP Sciences
VL - 46
IS - 1
SP - 67
EP - 76
AB - For an extensive range of infinite words, and the associated symbolic dynamical systems, we compute, together with the usual language complexity function counting the finite words, the minimal and maximal complexity functions we get by replacing finite words by finite patterns, or words with holes.
LA - eng
KW - Infinite words; symbolic dynamical systems; complexity; infinite words
UR - http://eudml.org/doc/277834
ER -

References

top
  1. P. Alesssandri, Codages de rotations et basses complexités. Université Aix-Marseille II, Ph.D. thesis (1996).  
  2. A. Avila and G. Forni, Weak mixing for interval exchange maps and translation flows, Ann. Math. (2)165 (2007) 637 − 664.  Zbl1136.37003
  3. G. Castiglione, A. Restivo and S. Salemi, Patterns in words and languages. Discrete Appl. Math.144 (2004) 237 − 246.  Zbl1088.68145
  4. J. Chaika, Topological mixing for some residual sets of interval exchange transformations. Preprint (2011).  Zbl1353.37080
  5. I.P. Cornfeld, S.V. Fomin and Y.G. Sinai, Ergodic theory. Translated from the Russian by A.B. Sosinski, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, New York 245 (1982) x+486. Zbl0493.28007
  6. E.M. Coven and G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theory7 (1973) 138–153.  Zbl0256.54028
  7. S. Ferenczi, Complexity of sequences and dynamical systems. Combinatorics and number theory (Tiruchirappalli, 1996). Discrete Math.206 (1999) 145–154.  Zbl0936.37008
  8. T. Kamae, Uniform sets and complexity. Discrete Math.309 (2009) 3738 − 3747.  Zbl1204.68150
  9. T. Kamae, Behavior of various complexity functions. Preprint (2011).  Zbl1260.68312
  10. T. Kamae and L. Zamboni, Sequence entropy and the maximal pattern complexity of infinite words. Ergod. Theory Dyn. Syst.22 (2002) 1191–1199.  Zbl1014.37004
  11. T. Kamae and L. Zamboni, Maximal pattern complexity for discrete systems. Ergod. Theory Dyn. Syst.22 (2002) 1201–1214.  Zbl1014.37003
  12. T. Kamae, H. Rao, B. Tan and Y.-M. Xue, Super-stationary set, subword problem and the complexity. Discrete Math.309 (2009) 4417–4427.  Zbl1217.68173
  13. M.S. Keane, Non-ergodic interval exchange transformations. Israe"l J. Math. 26 (1977), 188–196.  Zbl0351.28012
  14. D. Lind and B. Marcus, An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge (1995) xvi+495.  Zbl1106.37301
  15. M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938) 815–866.  Zbl64.0798.04
  16. M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math.62 (1940) 1 − 42.  Zbl66.0188.03
  17. N. Pytheas-Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math.1794, edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. Springer-Verlag, Berlin (2002).  Zbl1014.11015
  18. G. Rote, Sequences with subword complexity 2n. J. Number Theory46 (1994) 196–213.  Zbl0804.11023

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.