Three complexity functions
Ferenczi, Sébastien ; Hubert, Pascal
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012), p. 67-76 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2012-01-01
DOI : https://doi.org/10.1051/ita/2011126
Classification:  37B10,  68R15 
@article{ITA_2012__46_1_67_0,
     author = {Ferenczi, S\'ebastien and Hubert, Pascal},
     title = {Three complexity functions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {46},
     year = {2012},
     pages = {67-76},
     doi = {10.1051/ita/2011126},
     mrnumber = {2904961},
     zbl = {1271.37012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2012__46_1_67_0}
}

Ferenczi, Sébastien; Hubert, Pascal. Three complexity functions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 67-76. doi : 10.1051/ita/2011126. http://gdmltest.u-ga.fr/item/ITA_2012__46_1_67_0/

[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. | MR 2299743 | Zbl 1136.37003

[3] G. Castiglione, A. Restivo and S. Salemi, Patterns in words and languages. Discrete Appl. Math. 144 (2004) 237 − 246. | MR 2098180 | Zbl 1088.68145

[4] J. Chaika, Topological mixing for some residual sets of interval exchange transformations. Preprint (2011).

[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. | MR 832433 | Zbl 0493.28007

[6] E.M. Coven and G.A. Hedlund, Sequences with minimal block growth. Math. Syst. Theory 7 (1973) 138-153. | MR 322838 | Zbl 0256.54028

[7] S. Ferenczi, Complexity of sequences and dynamical systems. Combinatorics and number theory (Tiruchirappalli, 1996). Discrete Math. 206 (1999) 145-154. | MR 1665394 | Zbl 0936.37008

[8] T. Kamae, Uniform sets and complexity. Discrete Math. 309 (2009) 3738 − 3747. | MR 2537367 | Zbl 1204.68150

[9] T. Kamae, Behavior of various complexity functions. Preprint (2011). | MR 2887629 | Zbl 1260.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. | MR 1926282 | Zbl 1014.37004

[11] T. Kamae and L. Zamboni, Maximal pattern complexity for discrete systems. Ergod. Theory Dyn. Syst. 22 (2002) 1201-1214. | MR 1926283 | Zbl 1014.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. | MR 2519177 | Zbl 1217.68173

[13] M.S. Keane, Non-ergodic interval exchange transformations. Israe"l J. Math. 26 (1977), 188-196. | MR 435353 | Zbl 0351.28012

[14] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge (1995) xvi+495. | MR 1369092 | Zbl 1106.37301

[15] M. Morse and G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM 64.0798.04 | MR 1507944

[16] M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1 − 42. | JFM 66.0188.03 | MR 745

[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). | MR 1970385 | Zbl 1014.11015

[18] G. Rote, Sequences with subword complexity 2n. J. Number Theory 46 (1994) 196-213. | MR 1269252 | Zbl 0804.11023