Hereditary properties of words

József Balogh, Béla Bollobás

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)49-65
Number of pages17
JournalRAIRO - Theoretical Informatics and Applications
Volume39
Issue number1
DOIs
StatePublished - Jan 2005
Externally publishedYes

Keywords

  • Graph properties
  • Hereditary
  • Monotone
  • Size
  • Speed

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Hereditary properties of words'. Together they form a unique fingerprint.

Cite this