1.5. Перекрытие

По определению слово или ω-слово называется бесквадратным, если оно не содержит подслова вида xx, где x непусто. Может случиться, что слово w содержит два "перекрывающихся" вхождения x, т. е. подслово xy = zx, где

Если это не имеет места, то будем называть w словом без (или свободным от) перекрытий.

Следующая характеризационная лемма помимо всего прочего показывает, что рассматривавшиеся выше бесквадратные и сильно бескубные ω-слова являются также словами без перекрытий.

Лемма 1.10. Слово или ω-слово свободно от перекрытий тогда и только тогда, когда оно является сильно бескубным.

Доказательство. Пусть w не свободно от перекрытий. Тогда в w найдется подслово xy - zx, такое, что имеет место (1.16). Пусть а - первая буква слова z. По нашему предположению, x = zx₁, где первой буквой слова x₁ также будет a. Следовательно, zza - подслово w и w не является сильно бескубным.

Наоборот, предположим, что w не является сильно бескубным. Тогда в w найдется подслово z₁z₁a, где а - первая буква z₁. Полагая z₁ = az₂, мы видим, что az2az2a является полсловом w. Положим теперь x = az₂a, y = z₂a, z = az₂. Тогда xy = zx - подслово w, и, кроме того, выполняется (1.16). Отсюда следует, что w не свободно от перекрытий.▫

Туэ рассмотрел также понятие, более сильное, чем бесквадратность. Он называет ω-слово над алфавитом ∑, содержащим n букв, неприводимым в том случае, когда для любого подслова вида xyx (с непустым x) имеет место неравенство |y|≥n-2. Таким образом, при n = 3 это понятие совпадает с понятием бесквадратности. Неприводимое ω-слово может быть построено над любым алфавитом ∑. (Заметим, что при n≤2 каждое ω-слово тривиальным образом неприводимо.)

Можно усилить условие неперекрывающихся вхождений слова x в w, потребовав, чтобы длина слова y, разделяющего эти вхождения, была ограничена снизу |x|. В этом направлении можно установить следующий результат.

Теорема 1.11. Если ∑ содержит не менее трех букв, то существует такое ω-слово w над ∑, что для любого подслова xyx (x≠λ) ω-слова w имеет место |y|≥(¹/₃)|x|.

Доказательство этой теоремы дано в [De]. Искомое ω-слово порождается DOL-системой ({a, b, c}, h, a), где

В [De] обсуждается также вопрос, почему |h(a)| нельзя сделать меньше, и показывается, что постоянная ¹/₃ является наилучшей из возможных в следующем смысле. Пусть ∑ содержит три буквы. Тогда каждое слово над ∑ длины ≥39 содержит некоторое подслово xyx, такое, что x≠λ и |y|≤(¹/₃)|x|.