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.
Original language | English (US) |
---|---|
Pages (from-to) | 49-65 |
Number of pages | 17 |
Journal | RAIRO - Theoretical Informatics and Applications |
Volume | 39 |
Issue number | 1 |
DOIs | |
State | Published - 2005 |
Externally published | Yes |
Keywords
- Graph properties
- Hereditary
- Monotone
- Size
- Speed
ASJC Scopus subject areas
- Software
- Mathematics(all)
- Computer Science Applications