Hereditary properties of words

Balogh, 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 -