Hereditary properties of words

Issue		RAIRO-Theor. Inf. Appl. Volume 39, Number 1, January-March 2005 Imre Simon, the tropical computer scientist


Page(s)		49 - 65
DOI		10.1051/ita:2005003

Theoret. Informatics Appl. 39, 49-65 (2005)
DOI: 10.1051/ita:2005003

József Balogh¹ and Béla Bollobás²

¹ Department of Mathematical Sciences, The Ohio State University, Columbus, OH 43210, USA; jobal@math.ohio-state.edu
² Department of Mathematical Sciences, The University of Memphis, Memphis, TN 38152, and Trinity College, Cambridge CB2 1TQ, England; bollobas@msci.memphis.edu

Abstract
Let ${\mathcal 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 ${\mathcal P}$ is also in ${\mathcal P}$ . Extending the classical Morse-Hedlund theorem, we show that either ${\mathcal 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 ${\mathcal P}$ has $m\le n$ words of length n then, for every $k\ge n+m$ , it contains at most $\lceil (m+1)/2\rceil \lfloor (m+1)/2 \rfloor$ words of length k.

Mathematics Subject Classification. 05C

Key words: Graph properties -- monotone -- hereditary -- speed -- size.

© EDP Sciences 2005

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.