The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length . In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More precisely, for each sequence of subword complexity and for each prime we build a Toeplitz word on the same alphabet whose arithmetical complexity is .
Mots clés : arithmetical complexity, infinite word, subword complexity, Toeplitz word, bispecial words
@article{ITA_2006__40_3_443_0, author = {Frid, Anna E.}, title = {On possible growths of arithmetical complexity}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {443--458}, publisher = {EDP-Sciences}, volume = {40}, number = {3}, year = {2006}, doi = {10.1051/ita:2006021}, mrnumber = {2269203}, zbl = {1110.68120}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2006021/} }
TY - JOUR AU - Frid, Anna E. TI - On possible growths of arithmetical complexity JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 443 EP - 458 VL - 40 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006021/ DO - 10.1051/ita:2006021 LA - en ID - ITA_2006__40_3_443_0 ER -
%0 Journal Article %A Frid, Anna E. %T On possible growths of arithmetical complexity %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 443-458 %V 40 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006021/ %R 10.1051/ita:2006021 %G en %F ITA_2006__40_3_443_0
Frid, Anna E. On possible growths of arithmetical complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 443-458. doi : 10.1051/ita:2006021. http://www.numdam.org/articles/10.1051/ita:2006021/
[1] Palindrome complexity. Theoret. Comput. Sci. 292 (2003) 9-31. | MR | Zbl
, , and ,[2] Canonical positions for the factors in paperfolding sequences. Theoret. Comput. Sci. 129 (1994) 263-278. | MR | Zbl
and ,[3] Automatic sequences: theory, applications, generalizations. Cambridge Univ. Press (2003). | MR | Zbl
and ,[4] Sequences of low arithmetical complexity. submitted. | Numdam | MR | Zbl
, and ,[5] Arithmetical complexity of infinite words, in Words, Languages & Combinatorics III, Words, Languages & Combinatorics III, Singapore (2003), 51-62 World Scientific Publishing. ICWLC 2000, Kyoto, Japan, March (2000) 14-18.
, and ,[6] Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | EuDML | MR | Zbl
,[7] Constructing infinite words of intermediate complexity, in Developments in Language Theory VI, edited by M. Ito and M. Toyama. Lect. Notes Comput. Sci. 2450 (2003) 173-184. | MR | Zbl
,[8] On arithmetical complexity of Sturmian words, accepted to WORDS'05. | Zbl
and ,[9] Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Combin. 18 (1997) 497-510. | Zbl
and ,[10] Local symmetries in the period doubling sequence. Discrete Appl. Math. 100 (2000) 115-121. | Zbl
,[11] On the -complexity of words, Ann. Univ. Sci. Budapest. Sect. Comput. 8 (1987) 69-90. | Zbl
,[12] Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | Zbl
,[13] A lower bound for arithmetical complexity of Sturmian words. Siberian Electronic Math. Reports 2 (2005) 14-22. | EuDML | Zbl
,[14] Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci. 306 (2003) 535-542. | Zbl
,[15] Sequences of linear arithmetical complexity. Theoret. Comput. Sci. 339 (2005) 68-87. | Zbl
,[16] Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Syst. 22 (2002) 1191-1199. | Zbl
and ,[17] Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Syst. 22 (2002), 1201-1214. | Zbl
and ,[18] Maximal pattern complexity over letters. Eur. J. Combin., to appear. | Zbl
and ,[19] Two dimensional word with 2k maximal pattern complexity. Osaka J. Math. 41 (2004) 257-265. | Zbl
and ,[20] Complexités de suites de Toeplitz. Discrete Math. 183 (1998) 161-183. | Zbl
,[21] Modified complexity and *-Sturmian words. Proc. Japan Acad. Ser. A 75 (1999) 26-28. | Zbl
, and , , and , *-Sturmian words and complexity. J. Théorie des Nombres de Bordeaux 15 (2003) 767-804. |[23] Van der Waerden's theorem, in Combinatorics on words, edited by M. Lothaire. Addison-Wesley (1983) 39-54.
,[24] Binary patterns in infinite binary words, in Formal and Natural Computing, edited by W. Brauer et al. Lect. Notes Comput. Sci. 2300 (2002) 107-116. | Zbl
and ,[25] Beweis einer Baudet'schen Vermutung. Nieuw. Arch. Wisk. 15 (1927) 212-216. | JFM
,Cité par Sources :