Применение алгебраических методов в решении некоторых вопросов сложности комбинаторной теории слов и частично упорядоченных множеств

• Автор: Батуева, Цындыма Чимит-Доржиевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Новосибирск
• Количество страниц: 88 с. : ил.

Оглавление
Введение
1 Двумерные элементарные слова Тёплица
1.1 Арифметическое замыкание двумерных элементарных
слов Тёплица
1.1.1 Определения и обозначения
1.1.2 Связь арифметических подпоследовательностей в
неподвижных точках
1.1.3 Арифметическая сложность при простом т
1.1.4 Арифметическое замыкание для произвольных натуральных чисел т и I
1.2 Максимальная шаблонная сложностью двумерных элементарных слов Тёплица
1.2.1 Основные определения
1.2.2 Вспомогательные утверждения
1.2.3 Основная теорема
2 Частично упорядоченные множества
2.1 Решетки выпуклых подмножеств
2.1.1 Основные понятия
2.1.2 Характеризация класса Со(СРП)
2.1.3 Решетки выпуклых подмножеств п-арных лесов
2.2 Идеалы в частично упорядоченных множествах
2.2.1 Расширения и идеалы в частично упорядоченных
множествах
2.2.2 Представление простыми идеалами

2.2.3 Идеалы дистрибутивных частично упорядоченных множеств
2.2.4 Нормальные частично упорядоченные множества
Литература

Введение
Настоящая работа находится на стыке дискретной математики, универсальной алгебры и теории решеток. В ней с использованием комбинаторных и алгебраических методов, а также частично методов теории моделей изучаются классические комбинаторные объекты, такие как формальные языки и частично упорядоченные множества. Целью исследований, результаты которых изложены здесь, было изучение алгебраических и комбинаторных свойств, во-первых, двумерных слов над конечными алфавитами и, во-вторых, частично упорядоченных множеств, а также изучение сложности строения некоторых связанных с ними производных конструкций. Вопросы, изучаемые в настоящей диссертации, естественным образом возникли при изучении формальных языков и частично упорядоченных множеств, соответственно.
Задача построения двумерных слов небольшой комбинаторной сложности, а также получение точных формул для этой сложности являются актуальными проблемами теории формальных языков. Существуют определенные границы, за которыми всякое двумерное слово становится периодическим. Изучение слов, лежащих на этой границе и в непосредственной близости от нее, может иметь самые неожиданные следствия и приложения в таких областях, как теория кодирования, кристаллография, теория фракталов и др.
Рассмотрим бесконечное одномерное слово V — ь>(1)1)(2)г»(3)... над конечным алфавитом Е. Подсловом слова г> называется слово вида ь>(г)г>(г + 1).. у{г + п — 1) для некоторых г, п 6 N. Комбинаторная сложность р(п) слова V, введенная Эренфойхтом, Ли и Розенбергом [9] в 1975

Таким образом, получим, что фг(п) = п — при п Є [тг,тг+1
и всех г 1. Следовательно, нижняя граница для /(п) при гг 3 будет иметь вид --тг
т—1 т
Верхняя граница /(п) устанавливается аналогично. □
Теперь мы можем сформулировать первый основной результат этой диссертации.
Теорема 1.1.19 Пусть т — простое число. Арифметическая сложность двумерного элементарного слова Тёплица С¥{тіТО) растет линейно.
1.1.4 Арифметическое замыкание для произвольных натуральных чисел т и I
Рассмотрим теперь двумерное элементарное слово Тёплица где
произвольные натуральные числа т,1 2.
Лемма 1.1.20 Пусть т, I 2. Слово и Є С(т,1) тогда и только тогда, когда слово и или и являются подсловами одного из следующих слов:
(i) Т)ті{у), Т>т(и), Т>і(у), где V является подсловом Лтог(У) є П(т,і)> а слово Vі Є
(ii) Ър(у), где и является подсловом Т>ті(и') Є Т(т,/) т(и'), ®і(и') Є (т,і))> Р ~ делитель нок(т,1) (соответственно, т и I) и слово
Доказательство. Рассмотрим произвольное арифметическое подслово и двумерного элементарного слова Тёплица оцтуіу Существует арифметическая подпоследовательность 3(х,у,тг + Н,1в + Ф), где ц Є {О