# Hereditary properties of words

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

- 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 - Informatique Théorique et Applications 39.1 (2005): 49-65. <http://eudml.org/doc/244882>.

@article{Balogh2005,

abstract = {Let $\{\mathcal \{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 $\{\mathcal \{P\}\}$ is also in $\{\mathcal \{P\}\}$. Extending the classical Morse-Hedlund theorem, we show that either $\{\mathcal \{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 $\{\mathcal \{P\}\}$ has $m\le n$ words of length $n$ then, for every $k\ge n+m$, it contains at most $\lceil (m+1)/2\rceil \lfloor (m+1)/2 \rfloor $ words of length $k$.},

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

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

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

language = {eng},

number = {1},

pages = {49-65},

publisher = {EDP-Sciences},

title = {Hereditary properties of words},

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

volume = {39},

year = {2005},

}

TY - JOUR

AU - Balogh, József

AU - Bollobás, Béla

TI - Hereditary properties of words

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2005

PB - EDP-Sciences

VL - 39

IS - 1

SP - 49

EP - 65

AB - Let ${\mathcal {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 ${\mathcal {P}}$ is also in ${\mathcal {P}}$. Extending the classical Morse-Hedlund theorem, we show that either ${\mathcal {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 ${\mathcal {P}}$ has $m\le n$ words of length $n$ then, for every $k\ge n+m$, it contains at most $\lceil (m+1)/2\rceil \lfloor (m+1)/2 \rfloor $ words of length $k$.

LA - eng

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

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

ER -

## References

top- [1] S. Ferenczi, Rank and symbolic complexity. Ergodic Theory Dyn. Syst. 16 (1996) 663–682. Zbl0858.68051
- [2] S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145–154. Zbl0936.37008
- [3] N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109–114. Zbl0131.30203
- [4] A. Heinis, The $P\left(n\right)/n$-function for bi-infinite words. Theoret. Comput. Sci. 273 (2002) 35–46. Zbl1027.68654
- [5] 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
- [6] M. Morse and A.G. Hedlund, Symbolic dynamics. Amer. J. Math 60 (1938) 815–866. Zbl0019.33502JFM64.0798.04
- [7] R. Tijdeman, Periodicity and almost periodicity. Preprint, www.math.leidenuniv/$\sim $tijdeman Zbl1103.68103MR2223402

## NotesEmbed ?

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