Currently displaying 1 – 13 of 13

Showing per page

Order by Relevance | Title | Year of publication

Hereditary properties of words

József Balogh;  Béla Bollobás — 2005

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

Let 𝒫 be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to 𝒫 is also in 𝒫 . Extending the classical Morse-Hedlund theorem, we show that either 𝒫 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 𝒫 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...

Hereditary properties of words

József Balogh;  Béla Bollobás — 2010

RAIRO - Theoretical Informatics and Applications

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

Page 1

Download Results (CSV)