×

On possible growths of arithmetical complexity. (English) Zbl 1110.68120

Summary: The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n 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 n. 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 u of subword complexity fu(n) and for each prime \(p \geq 3\) we build a Toeplitz word on the same alphabet whose arithmetical complexity is \(a(n)=\Theta(n f_u(\lceil \log_p n \rceil))\).

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML Link

References:

[1] J.-P. Allouche , M. Baake , J. Cassaigne and D. Damanik , Palindrome complexity . Theoret. Comput. Sci. 292 ( 2003 ) 9 - 31 . Zbl 1064.68074 · Zbl 1064.68074 · doi:10.1016/S0304-3975(01)00212-2
[2] J.-P. Allouche and M. Bousquet-Mélou , Canonical positions for the factors in paperfolding sequences . Theoret. Comput. Sci. 129 ( 1994 ) 263 - 278 . Zbl 0820.11011 · Zbl 0820.11011 · doi:10.1016/0304-3975(94)90028-0
[3] J.-P. Allouche and J. Shallit , Automatic sequences: theory, applications, generalizations . Cambridge Univ. Press ( 2003 ). MR 1997038 | Zbl 1086.11015 · Zbl 1086.11015 · doi:10.1017/CBO9780511546563
[4] S.V. Avgustinovich , J. Cassaigne and A.E. Frid , Sequences of low arithmetical complexity . submitted. Numdam | Zbl 1110.68116 · Zbl 1110.68116 · doi:10.1051/ita:2006041
[5] S.V. Avgustinovich , D.G. Fon-Der-Flaass and A.E. Frid , 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 .
[6] J. Cassaigne , Complexité et facteurs spéciaux . Bull. Belg. Math. Soc. Simon Stevin 4 ( 1997 ) 67 - 88 . Article | Zbl 0921.68065 · Zbl 0921.68065
[7] J. Cassaigne , 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 . Zbl 1015.68138 · Zbl 1015.68138
[8] J. Cassaigne and A. Frid , On arithmetical complexity of Sturmian words, accepted to WORDS’05 . · Zbl 1119.68138
[9] J. Cassaigne and J. Karhumäki , Toeplitz words, generalized periodicity and periodically iterated morphisms . Eur. J. Combin. 18 ( 1997 ) 497 - 510 . Zbl 0881.68065 · Zbl 0881.68065 · doi:10.1006/eujc.1996.0110
[10] D. Damanik , Local symmetries in the period doubling sequence . Discrete Appl. Math. 100 ( 2000 ) 115 - 121 . Zbl 0943.68127 · Zbl 0943.68127 · doi:10.1016/S0166-218X(99)00199-7
[11] A. Iványi , On the \(d\)-complexity of words , Ann. Univ. Sci. Budapest. Sect. Comput. 8 ( 1987 ) 69 - 90 . Zbl 0663.68085 · Zbl 0663.68085
[12] S. Ferenczi , Complexity of sequences and dynamical systems . Discrete Math. 206 ( 1999 ) 145 - 154 . Zbl 0936.37008 · Zbl 0936.37008 · doi:10.1016/S0012-365X(98)00400-2
[13] A. Frid , A lower bound for arithmetical complexity of Sturmian words . Siberian Electronic Math. Reports 2 ( 2005 ) 14 - 22 . Zbl 1125.68091 · Zbl 1125.68091
[14] A. Frid , Arithmetical complexity of symmetric D0L words . Theoret. Comput. Sci. 306 ( 2003 ) 535 - 542 . Zbl 1070.68068 · Zbl 1070.68068 · doi:10.1016/S0304-3975(03)00345-1
[15] A. Frid , Sequences of linear arithmetical complexity . Theoret. Comput. Sci. 339 ( 2005 ) 68 - 87 . Zbl 1076.68053 · Zbl 1076.68053 · doi:10.1016/j.tcs.2005.01.009
[16] T. Kamae and L. Zamboni , Sequence entropy and the maximal pattern complexity of infinite words . Ergodic Theory Dynam. Syst. 22 ( 2002 ) 1191 - 1199 . Zbl 1014.37004 · Zbl 1014.37004 · doi:10.1017/S014338570200055X
[17] T. Kamae and L. Zamboni , Maximal pattern complexity for discrete systems . Ergodic Theory Dynam. Syst. 22 ( 2002 ), 1201 - 1214 . Zbl 1014.37003 · Zbl 1014.37003 · doi:10.1017/S0143385702000585
[18] T. Kamae and H. Rao , Maximal pattern complexity over \(\ell \) letters . Eur. J. Combin., to appear. Zbl 1082.68090 · Zbl 1082.68090 · doi:10.1016/j.ejc.2004.07.006
[19] T. Kamae and Y.-M. Xue , Two dimensional word with 2k maximal pattern complexity . Osaka J. Math. 41 ( 2004 ) 257 - 265 . Article | Zbl 1053.37004 · Zbl 1053.37004
[20] M. Koskas , Complexités de suites de Toeplitz . Discrete Math. 183 ( 1998 ) 161 - 183 . Zbl 0895.11011 · Zbl 0895.11011 · doi:10.1016/S0012-365X(96)00077-5
[21] I. Nakashima , J. Tamura and S. Yasutomi , Modified complexity and *-Sturmian words. Proc. Japan Acad. Ser. A 75 (1999) 26-28. Article | Zbl 0928.11012 · Zbl 0928.11012 · doi:10.3792/pjaa.75.26
[22] I. Nakashima , J.-I. Tamura and S.-I. Yasutomi , *-Sturmian words and complexity. J. Théorie des Nombres de Bordeaux 15 (2003) 767-804. Numdam | Zbl pre02184624 · Zbl 1155.68479 · doi:10.5802/jtnb.426
[23] J.-E. Pin , Van der Waerden’s theorem , in Combinatorics on words, edited by M. Lothaire. Addison-Wesley ( 1983 ) 39 - 54 .
[24] A. Restivo and S. Salemi , 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 1060.68098 · Zbl 1060.68098
[25] B.L. Van der Waerden , Beweis einer Baudet’schen Vermutung . Nieuw. Arch. Wisk. 15 ( 1927 ) 212 - 216 . JFM 53.0073.12 · JFM 53.0073.12
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.