Back to Search
Start Over
On maximal pattern complexity of some automatic words
- Source :
- Ergodic Theory and Dynamical Systems. 31:1463-1470
- Publication Year :
- 2010
- Publisher :
- Cambridge University Press (CUP), 2010.
-
Abstract
- The pattern complexity of a word for a given pattern S, where S is a finite subset of {0,1,2,…}, is the number of distinct restrictions of the word to S+n (with n=0,1,2,…). The maximal pattern complexity of the word, introduced in the paper of T. Kamae and L. Zamboni [Sequence entropy and the maximal pattern complexity of infinite words. Ergod. Th. & Dynam. Sys.22(4) (2002), 1191–1199], is the maximum value of the pattern complexity of S with #S=k as a function of k=1,2,…. A substitution of constant length on an alphabet is a mapping from the alphabet to finite words on it of constant length not less than two. An infinite word is called a fixed point of the substitution if it stays the same after the substitution is applied. In this paper, we prove that the maximal pattern complexity of a fixed point of a substitution of constant length on {0,1} (as a function of k=1,2,…) is either bounded, a linear function of k, or 2k.
Details
- ISSN :
- 14694417 and 01433857
- Volume :
- 31
- Database :
- OpenAIRE
- Journal :
- Ergodic Theory and Dynamical Systems
- Accession number :
- edsair.doi...........bd290d8c78edb239c963365137cc77a3