Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T18:07:02.888Z 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: kamae@apost.plala.or.jp)
PAVEL V. SALIMOV
Affiliation:
Sobolev Institute of Mathematics, prosp. Koptyuga 4, 630090 Novosibirsk, Russia (email: ch.cat.s.smile@gmail.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

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

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