# Hereditary properties of words

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 39, Issue: 1, page 49-65
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBalogh, József, and Bollobás, Béla. "Hereditary properties of words." RAIRO - Theoretical Informatics and Applications 39.1 (2010): 49-65. <http://eudml.org/doc/92765>.

@article{Balogh2010,

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.
},

author = {Balogh, József, Bollobás, Béla},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = { Graph properties; monotone;
hereditary; speed; size.; graph property; hereditary; dynamic symbolic},

language = {eng},

month = {3},

number = {1},

pages = {49-65},

publisher = {EDP Sciences},

title = {Hereditary properties of words},

url = {http://eudml.org/doc/92765},

volume = {39},

year = {2010},

}

TY - JOUR

AU - Balogh, József

AU - Bollobás, Béla

TI - Hereditary properties of words

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 39

IS - 1

SP - 49

EP - 65

AB -
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.

LA - eng

KW - Graph properties; monotone;
hereditary; speed; size.; graph property; hereditary; dynamic symbolic

UR - http://eudml.org/doc/92765

ER -

## References

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

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.