A combinatorial property of EOL languages

Abstract

Let Δ be an alphabet and II its nontrivial binary partition. Each word over Δ can uniquely be decomposed in subwords (called blocks) consisting of letters of II _i only,i ∈ {1,2}. LetK $\subseteq$ Δ^*.K has a long block property (with respect to II), abbreviated asLB-property, if there exists a functionf:N ⁺ →N ⁺ such that for everyw ∈K and every positive integerm the number of blocks of length at mostm inw is bounded byf(m). K has a clustered block property (with respect to II), abbreviated asCB-property, if there exists a positive integern _o and a growing functiong:N ⁺ →N ⁺ such that for everyw ∈K and for every positive integerm the blocks of length at mostm can be covered by at mostn _o segments of length at mostg(m).

It is proved that aCB-property always implies aLB-property but not necessarily other way around. It is proved that an EOL language has aLB-property if and only if it has aCB-property.