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 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 words of length .
Mots-clés : graph properties, monotone, hereditary, speed, size
@article{ITA_2005__39_1_49_0, author = {Balogh, J\'ozsef and Bollob\'as, B\'ela}, title = {Hereditary properties of words}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {49--65}, publisher = {EDP-Sciences}, volume = {39}, number = {1}, year = {2005}, doi = {10.1051/ita:2005003}, mrnumber = {2132578}, zbl = {1132.68048}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2005003/} }
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 SP - 49 EP - 65 VL - 39 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2005003/ DO - 10.1051/ita:2005003 LA - en ID - ITA_2005__39_1_49_0 ER -
%0 Journal Article %A Balogh, József %A Bollobás, Béla %T Hereditary properties of words %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 49-65 %V 39 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2005003/ %R 10.1051/ita:2005003 %G en %F ITA_2005__39_1_49_0
Balogh, József; Bollobás, Béla. Hereditary properties of words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 1, pp. 49-65. doi : 10.1051/ita:2005003. http://archive.numdam.org/articles/10.1051/ita:2005003/
[1] Rank and symbolic complexity. Ergodic Theory Dyn. Syst. 16 (1996) 663-682. | Zbl
,[2] Complexity of sequences and dynamical systems. Discrete Math. 206 (1999) 145-154. | Zbl
,[3] Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc. 16 (1965) 109-114. | Zbl
and ,[4] The -function for bi-infinite words. Theoret. Comput. Sci. 273 (2002) 35-46. | Zbl
,[5] Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Syst. 22 (2002) 1191-1199. | Zbl
and ,[6] Symbolic dynamics. Amer. J. Math 60 (1938) 815-866. | JFM
and , ,Cité par Sources :