Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-24T15:41:49.810Z Has data issue: false hasContentIssue false
  • English
  • Français

On maximal pattern complexity of some automatic words

Published online by Cambridge University Press:  13 October 2010

TETURO KAMAE  and
PAVEL V. SALIMOV
TETURO KAMAE
Affiliation:
Satakedai 5-9-6, Suita 565-0855, Japan (email: [email protected])
PAVEL V. SALIMOV
Affiliation:
Sobolev Institute of Mathematics, prosp. Koptyuga 4, 630090 Novosibirsk, Russia (email: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 31 , Issue 5 , October 2011 , pp. 1463 - 1470
Copyright
Copyright © Cambridge University Press 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Allouche, J.-P. and Shallit, J.. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge, 2003.CrossRefGoogle Scholar
[2]Avgustinovich, S. V., Cassaigne, J. and Frid, A. E.. Sequences of low arithmetical complexity. Theor. Inform. Appl. 40 (2006), 569–582.CrossRefGoogle Scholar
[3]Avgustinovich, S. V., Fon-Der-Flaass, D. G. and Frid, A. E.. Arithmetical complexity of infinite words. Words, Languages and Combinatorics III. Eds. Ito, M. and Imaoka, T.. World Scientific, Singapore, 2003, pp. 51–62.CrossRefGoogle Scholar
[4]Cassaigne, J. and Karhumäki, J.. Toeplitz words, generalized periodicity and periodically iterated morphisms. European J. Combin. 18 (1997), 497–510.CrossRefGoogle Scholar
[5]Ferenczi, S.. Complexity of sequences and dynamical systems. Discrete Math. 206(1) (1999), 145–154.CrossRefGoogle Scholar
[6]Frid, A. E.. Arithmetical complexity of symmetric D0L words. Theoret. Comput. Sci. 306(1) (2003), 535–542.CrossRefGoogle Scholar
[7]Gjini, N., Kamae, T., Tan, B. and Xue, Y.-M.. Maximal pattern complexity for Toeplitz words. Ergod. Th. & Dynam. Sys. 26 (2006), 1–14.CrossRefGoogle Scholar
[8]Jacobs, K. and Keane, M.. 0-1 sequences of Toeplitz type. Z. Wahrscheinlichkeitstheor. Verwandte. Geb. 13 (1969), 123–131.CrossRefGoogle Scholar
[9]Kamae, T.. Maximal pattern complexity as topological invariants. Preprint, 2006,http://www14.plala.or.jp/kamae.Google Scholar
[10]Kamae, T. and Zamboni, L.. Sequence entropy and the maximal pattern complexity of infinite words. Ergod. Th. & Dynam. Sys. 22(4) (2002), 1191–1199.CrossRefGoogle Scholar