Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-29T04:30:42.428Z Has data issue: false hasContentIssue false
  • English
  • Français

Hereditary properties of words

Published online by Cambridge University Press:  15 March 2005

József Balogh  and
Béla Bollobás
József Balogh
Affiliation:
Department of Mathematical Sciences, The Ohio State University, Columbus, OH 43210, USA; [email protected]
Béla Bollobás
Affiliation:
Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, and Trinity College, Cambridge CB2 1TQ, England; [email protected]
Get access

Abstract

Let P be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to P is also in P. Extending the classical Morse-Hedlund theorem, we show that either P contains at least n+1 words of length n for every n or, for some N, it contains at most N words of length n for every n. More importantly, we prove the following quantitative extension of this result: if P has m ≤ n words of length n then, for every k ≥ n + m, it contains at most ⌈(m + 1)/2⌉⌈(m + 1)/2⌈ words of length k.

Keywords

Graph propertiesmonotonehereditaryspeedsize.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 39 , Issue 1: Imre Simon, the tropical computer scientist , January 2005 , pp. 49 - 65
Copyright
© EDP Sciences, 2005

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

Ferenczi, S., Rank and symbolic complexity. Ergodic Theory Dyn. Syst. 16 (1996) 663–682. CrossRef
Ferenczi, S., Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145–154. CrossRef
Fine, N.J. and Wilf, H.S., Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. CrossRef
Heinis, A., The P(n)/n-function for bi-infinite words. Theoret. Comput. Sci. 273 (2002) 35–46. CrossRef
Kamae, T. and Zamboni, L., Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Syst. 22 (2002) 1191–1199.
Morse, M. and Hedlund, A.G., Symbolic dynamics. Amer. J. Math 60 (1938) 815–866. CrossRef
R. Tijdeman, Periodicity and almost periodicity. Preprint, www.math.leidenuniv/~tijdeman