О комбинаторных свойствах бесконечных слов, порожденных итерациями морфизмов

• Автор: Фрид, Анна Эдуардовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Новосибирск
• Количество страниц: 100 с. : ил

Оглавление
Введение

1. Обзор основных понятий

1.1. Формальные языки и Б ОЬ слова

1.2. Виды морфизмов

1.3. Циркулярность

1.4. Функции от бесконечных слов

2. Критерий циркулярности равноблочных буферных ЮОЬ слов

2.1. Формулировка критерия

2.2. Доказательство критерия

2.3. Множество слов без точек синхронизации

2.4. Проверка критерия
2.5. Случай бинарного алфавита
3. Свойства равноблочных буферных БОЬ слов
3.1. Соотношение на допустимые слова
3.2. Комбинаторная сложность
3.3. Частоты слов
3.4. Функция рекуррентности и родственные ей
4. Комбинаторная сложность бипрефиксных 1)0Г. слов
4.1. Сложность и биспециальные слова

4.2. Алгоритм Кассеня
4.3. От алгоритма к формуле
4.4. Пример
Библиография

Введение
В настоящей работе исследуются свойства БОЬ слов — бесконечных символьных последовательностей, порожденных итерациями морфизмов.
Пусть дан конечный алфавит 2 и морфизм ір : 2* -> 2*, то есть отображение, для любых слов ху над 2 удовлетворяющее равенству <р[ху) = (р(х)'р(у). Пусть образ <р(а) некоторого символа а алфавита 2 начинается с а. Тогда, как нетрудно видеть, существует конечное или бесконечное слово и>, начинающееся с а и удовлетворяющее равенству

Слово ад называется неподвижной точкой морфизма или БОЬ словом.
БОЬ слова представляют собой один из простейших по способу задания классов бесконечных непериодических последовательностей. Введенные первоначально в 1968 году для моделирования развития живых организмов [6], впоследствии они нашли применение во многих областях математики и теоретической кибернетики. Причиной этому послужили, с одной стороны, близость механизма их порождения к теории автоматов, а с другой — их фракталоподобная структура, привлекающая внимание специалистов в теории динамических систем [64].
В настоящее время БОЬ слова активно используются в случаях, когда требуется построить пример бесконечного слова с заданны-

отношениям I < mN яр + N' = 1 (mod к). Слово ау> имеет длину I и по построению принадлежит обоим классам С(Ар+у') и С(Д.+у/), где индексы берутся по модулю к: другими словами, Ар+у' = Ai, а Аг+у> = Ak~r+p+1- Равенство С{А) = C(Aj,_r+j,+i) может быть переписано в виде Су = Су+ь = Cft-p+r- Однако по условию 0 < г—р < к, что противоречит выбору к как минимального положительного числа, удовлетворяющего равенству Су = Су+fc- Противоречие. Множество {Ai,..., Ак} является ^-связанным.
Мы рассмотрели все возможные случаи нециркулярности слова го (ip) и в каждом из них нашли (^-связанное множество. Теорема доказана.
2.3. Множество слов без точек синхронизации
Пусть ip — равноблочный буферный морфизм. Символ алфавита Е мощности q назовем p-связанным, если он встречается в элементе какого-либо ^-связанного множества. Количество (^-связанных символов назовем числом нециркулярности морфизма р. Такое название может быть обосновано следующим фактом, напрямую вытекающим из теоремы 2.1:
Следствие 2.2. Неподвижная точка w{p) циркулярна тогда и только тогда, когда d(tp) = 0.
Пример 2.4. Для морфизма Туэ-Морса, морфизма Серпинского и морфизма (ри из примера 2.2 число нециркулярности равно соответственно 0, 1 и 4.
В общем случае, очевидно, 0 < d( Предложение 2.3. Пусть буферная длина морфизма р не равна нулю. Тогда d(p) < 1.