Page 1 Next

Displaying 1 – 20 of 28

Showing per page

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

Histoires de fichiers

Jean Françon (1978)

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

Currently displaying 1 – 20 of 28

Page 1 Next