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.
Mots clés : infinite words, symbolic dynamical systems, complexity
@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},
pages = {67--76},
publisher = {EDP-Sciences},
volume = {46},
number = {1},
year = {2012},
doi = {10.1051/ita/2011126},
mrnumber = {2904961},
zbl = {1271.37012},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2011126/}
}
TY - JOUR AU - Ferenczi, Sébastien AU - Hubert, Pascal TI - Three complexity functions JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 67 EP - 76 VL - 46 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2011126/ DO - 10.1051/ita/2011126 LA - en ID - ITA_2012__46_1_67_0 ER -
%0 Journal Article %A Ferenczi, Sébastien %A Hubert, Pascal %T Three complexity functions %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 67-76 %V 46 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2011126/ %R 10.1051/ita/2011126 %G en %F 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) no. 1, pp. 67-76. doi : 10.1051/ita/2011126. http://archive.numdam.org/articles/10.1051/ita/2011126/
[1] , Codages de rotations et basses complexités. Université Aix-Marseille II, Ph.D. thesis (1996).
[2] and , Weak mixing for interval exchange maps and translation flows, Ann. Math. (2) 165 (2007) 637 − 664. | MR | Zbl
[3] , and , Patterns in words and languages. Discrete Appl. Math. 144 (2004) 237 − 246. | MR | Zbl
[4] , Topological mixing for some residual sets of interval exchange transformations. Preprint (2011).
[5] , and , 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 | Zbl
[6] and , Sequences with minimal block growth. Math. Syst. Theory 7 (1973) 138-153. | MR | Zbl
[7] , Complexity of sequences and dynamical systems. Combinatorics and number theory (Tiruchirappalli, 1996). Discrete Math. 206 (1999) 145-154. | MR | Zbl
[8] , Uniform sets and complexity. Discrete Math. 309 (2009) 3738 − 3747. | MR | Zbl
[9] , Behavior of various complexity functions. Preprint (2011). | MR | Zbl
[10] and , Sequence entropy and the maximal pattern complexity of infinite words. Ergod. Theory Dyn. Syst. 22 (2002) 1191-1199. | MR | Zbl
[11] and , Maximal pattern complexity for discrete systems. Ergod. Theory Dyn. Syst. 22 (2002) 1201-1214. | MR | Zbl
[12] , , and , Super-stationary set, subword problem and the complexity. Discrete Math. 309 (2009) 4417-4427. | MR | Zbl
[13] , Non-ergodic interval exchange transformations. Israe"l J. Math. 26 (1977), 188-196. | MR | Zbl
[14] and , An introduction to symbolic dynamics and coding. Cambridge University Press, Cambridge (1995) xvi+495. | MR | Zbl
[15] and , Symbolic dynamics. Amer. J. Math. 60 (1938) 815-866. | JFM | MR
[16] and , Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1 − 42. | JFM | MR
[17] , 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 | Zbl
[18] , Sequences with subword complexity 2n. J. Number Theory 46 (1994) 196-213. | MR | Zbl
Cité par Sources :
