1.6. DOL-системы и ω-слова

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

Заметим, что ω-слово а из теоремы 1.5 порождается также DOL-системой

равно как и DOL-системой

Это частный случай следующего более общего результата, доказательство которого следует непосредственно из определений.

Лемма 1.12. Предположим, что δ является ω-словом, порождаемым DOL-системой (∑, h, w), и что i≥1, j≥0 - целые числа. Тогда δ порождается также DOL-системой (∑, hⁱ, h^j(w)).

Может случиться также, что исходная DOL-система не порождает никакого со-слова, но существуют такие натуральные числа i и j, что DOL-система (∑, hⁱ, h^j(w)) порождает некоторое ω-слово. Подобный пример приводится в упр. 14, а в упр. 15 обсуждается вопрос о существовании таких чисел.

В общем случае вопрос о том, порождают ли две DOL-системы G₁ и G₂ (удовлетворяющие дополнительному условию для порождения ω-слов) одно и то же ω-слово, достаточно труден. Эта проблема тесно связана с проблемой последовательностной эквивалентности для DOL-систем, которая будет рассмотрена ниже (см. гл. 5). Если G₁ и G₂ последовательностно эквивалентны (т. е. S(G₁) = S(G₂)), то они порождают одно и то же ω-слово. Обратное не обязательно верно, как показывает лемма 1.12.

Трудно бывает сказать, порождается ли данное ω-слово, определенное некоторым эффективным способом, некоторой DOL-системой. Этот вопрос можно сформулировать как точную (алгоритмическую) проблему разрешения для каждого класса эффективных методов задания ω-слов.

Например, ω-слово β из леммы 1.6 было задано сначала не с помощью DOL-системы. Однако β порождается DOL-системой ({1, 2, 3, 4}, h, 2), где

Общий метод решения проблемы бесквадратности ω-слова, порожденного DOL-системой G, пока неизвестен. В [Bel] дается такой метод для случая, когда алфавит G состоит из трех букв.

Мы будем говорить, что морфизм h сохраняет бесквадратность, если h(x) является бесквадратным всегда, когда бесквадратно x. Очевидно, что ω-слово δ, порожденное DOL-системой (∑, h, w), где w бесквадратно, а h сохраняет бесквадратность, само является бесквадратным (если, конечно, удовлетворяются условия порождения ω-слова). Например, в [Т2] Туэ показывает, что морфизм h₁, определенный равенствами

сохраняет бесквадратность. Таким образом, DOL-система ({a, b, c), h₁, a) порождает бесквадратное ω-слово. В то же время DOL-система (∑, h, w) может порождать бесквадратное ω-слово даже в том случае, когда h не сохраняет бесквадратность. Примером служит DOL-система ({a, b, c}, h₂, a), где h₂ задается равенствами

Можно показать, что порожденное этой системой ω-слово бесквадратно. Однако h₂ не сохраняет бесквадратность, так как