On possible growths of arithmetical complexity
RAIRO - Theoretical Informatics and Applications (2006)
- Volume: 40, Issue: 3, page 443-458
- ISSN: 0988-3754
Access Full Article
topAbstract
topHow to cite
topReferences
top- J.-P. Allouche, M. Baake, J. Cassaigne and D. Damanik, Palindrome complexity. Theoret. Comput. Sci.292 (2003) 9–31.
- J.-P. Allouche and M. Bousquet-Mélou, Canonical positions for the factors in paperfolding sequences. Theoret. Comput. Sci.129 (1994) 263–278.
- J.-P. Allouche and J. Shallit, Automatic sequences: theory, applications, generalizations. Cambridge Univ. Press (2003).
- S.V. Avgustinovich, J. Cassaigne and A.E. Frid, Sequences of low arithmetical complexity. submitted.
- 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.
- J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.
- 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.
- J. Cassaigne and A. Frid, On arithmetical complexity of Sturmian words, accepted to WORDS'05.
- J. Cassaigne and J. Karhumäki, Toeplitz words, generalized periodicity and periodically iterated morphisms. Eur. J. Combin.18 (1997) 497–510.
- D. Damanik, Local symmetries in the period doubling sequence. Discrete Appl. Math.100 (2000) 115–121.
- A. Iványi, On the d-complexity of words, Ann. Univ. Sci. Budapest. Sect. Comput.8 (1987) 69–90.
- S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154.
- A. Frid, A lower bound for arithmetical complexity of Sturmian words. Siberian Electronic Math. Reports2 (2005) 14–22.
- A. Frid, Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci.306 (2003) 535–542.
- A. Frid, Sequences of linear arithmetical complexity. Theoret. Comput. Sci.339 (2005) 68–87.
- T. Kamae and L. Zamboni, Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Syst.22 (2002) 1191–1199.
- T. Kamae and L. Zamboni, Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Syst.22 (2002), 1201–1214.
- T. Kamae and H. Rao, Maximal pattern complexity over l letters. Eur. J. Combin., to appear.
- T. Kamae and Y.-M. Xue, Two dimensional word with 2k maximal pattern complexity. Osaka J. Math.41 (2004) 257–265.
- M. Koskas, Complexités de suites de Toeplitz. Discrete Math.183 (1998) 161–183.
- I. Nakashima, J. Tamura and S. Yasutomi, Modified complexity and *-Sturmian words. Proc. Japan Acad. Ser. A75 (1999) 26–28.
- I. Nakashima, J.-I. Tamura and S.-I. Yasutomi, *-Sturmian words and complexity. J. Théorie des Nombres de Bordeaux15 (2003) 767–804.
- J.-E. Pin, Van der Waerden's theorem, in Combinatorics on words, edited by M. Lothaire. Addison-Wesley (1983) 39–54.
- 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.
- B.L. Van der Waerden, Beweis einer Baudet'schen Vermutung. Nieuw. Arch. Wisk.15 (1927) 212–216.