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