Hereditary properties of words
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 39, Issue: 1, page 49-65
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topBalogh, 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 -
References
top- S. Ferenczi, Rank and symbolic complexity. Ergodic Theory Dyn. Syst.16 (1996) 663–682. Zbl0858.68051
- S. Ferenczi, Complexity of sequences and dynamical systems. Discrete Math.206 (1999) 145–154. Zbl0936.37008
- N.J. Fine and H.S. Wilf, Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc.16 (1965) 109–114. Zbl0131.30203
- A. Heinis, The P(n)/n-function for bi-infinite words. Theoret. Comput. Sci.273 (2002) 35–46. Zbl1027.68654
- T. Kamae and L. Zamboni, Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Syst.22 (2002) 1191–1199. Zbl1014.37004
- M. Morse and A.G. Hedlund, Symbolic dynamics. Amer. J. Math60 (1938) 815–866. Zbl0019.33502
- R. Tijdeman, Periodicity and almost periodicity. Preprint, www.math.leidenuniv/~tijdeman Zbl1103.68103
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.