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




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

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

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

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

G1 = ({a, b}, h, abba), где h(a) = ab, h(b) = ba,

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

G2 = ({a, b], h1, а), где h1(a) = abba, h1(b) = baab.

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

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

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

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

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

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

h (1) = 2431, h (2) = 2432, h (3) = 3123, h (4) = 3124.

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

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

h1(a) = abcab, h1(b) = acabcb, h1(c) = acbcacb,

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

h2(a) = abc, h2(b) = ac, h2(c) = b.

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

h2(aba) = abcacabc.
предыдущая главасодержаниеследующая глава








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