НОВОСТИ   БИБЛИОТЕКА   ЮМОР   КАРТА САЙТА   ССЫЛКИ   О САЙТЕ  




предыдущая главасодержаниеследующая глава

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

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

1≤|y|=|z|<|x|.(1.16)

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

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

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

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

Наоборот, предположим, что w не является сильно бескубным. Тогда в w найдется подслово z1z1a, где а - первая буква z1. Полагая z1 = az2, мы видим, что az2az2a является полсловом w. Положим теперь x = az2a, y = z2a, z = az2. Тогда 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|≥(1/3)|x|.

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

h (a) = abc acb cab c bac bca cba,
h (b) = bca bac abc a cba cab acb,
h (c) = cab cba bca b acb abc bac.

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

предыдущая главасодержаниеследующая глава








© Злыгостев А.С., 2001-2019
При использовании материалов сайта активная ссылка обязательна:
http://informaticslib.ru/ 'Библиотека по информатике'
Рейтинг@Mail.ru