Комбинаторные свойства частичных слов

• Автор: Гамзова, Юлия Васильевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Екатеринбург
• Количество страниц: 98 с. : ил.

1°. Понятие о частичных словах
2°. Определения и обозначения
3°. Краткий обзор исследований по частичным словам
4°. Вопросы, рассматриваемые в диссертации
5°. Основные результаты диссертации
I Свойство взаимодействия периодов
§1 Существование длины взаимодействия
§2 Точные оценки в частных случаях
§3 Формулировка прямой и обратной задачи. Бланки и расстановки
§4 Решение обратной задачи
§5 Решение исходной задачи
II Статистические закономерности
§6 Идея алгоритма
§7 Количество расстановок с заданной характеристической расстановкой
§8 Построение вспомогательных таблиц
§9 Анализ полученных результатов
III Свойство взаимодействия локальных периодов
§10 Используемая техника
§11 Разрезы
§12 Алгоритм проверки наличия в расстановке специальной
подпоследовательности
§13 Модификации алгоритма

1°. Понятие о частичных словах
Символьные последовательности, или слова, представляют собой важный и популярный объект комбинаторных исследований. Задачи, связанные со словами, возникали в различных областях математики и других наук и привели к возникновению отдельного раздела дискретной математики, занимающейся изучением комбинаторных свойств слов. Историю комбинаторики слов принято отсчитывать от 1906 года, когда была опубликована работа [1]. С тех пор комбинаторика слов плодотворно развивалась и к настоящему времени обрела четкие контуры и собственную богатую проблематику. Имеющаяся литература весьма обширна. Упомянем здесь монографии [2-4], а также [5] и ряд других глав трехтомного «Справочника по формальным языкам».
Частичные слова представляют собой естественное обобщение понятия обычного слова. Частичное слово — это обычное слово, в котором часть букв по каким-то причинам отсутствует. Изучение комбинаторных свойств частичных слов «в явном виде» началось совсем недавно, в 1999 году, с работы [6].
Задачи, в которых возникают частичные слова, можно разделить на два типа. В задачах первого типа некоторая часть информации нам не важна (вне зависимости от того, доступна она или нет). Примером может служить задача поиска в тексте по шаблону, когда шаблон содержит символ (или символы) со значением «что угодно». В задачах второго типа некоторая часть информации для нас важна, но по каким-либо причинам недоступна. По имеющейся части информации и некоторым дополнительным условиям необходимо полностью восстановить информацию. Примером является задача восстановления фрагментов файлов, повреждённых при передаче или в результате порчи носителя. Очень интересными представляются также задачи молекулярной биологии (см. [7]), в частности, задача реконструкции нуклеотидных цепочек ДНК по частично расшифрованным фрагментам.

В данной работе изучаются комбинаторные свойства частичных слов, связанные с локальной и глобальной периодичностью.
2°. Определения и обозначения
1. Пусть А — конечный алфавит, А+ и А* — соответственно свободная полугруппа и свободный моноид над этим алфавитом. Элементы из А+ и А* называются словами, а множества слов — языками. Длина слова W обозначается через W. Для данной буквы а £ А обозначим через Ua количество букв а в слове U. На слово длины п можно смотреть как на функцию из множества {1,... ,п} в алфавит. Частичное слово длины п над алфавитом А — это частичная функция
Значение IV(г) мы будем называть буквой в і-ой позиции слова IV. Слова (обычные и частичные) мы обозначаем буквами Р, ф, Р, 5, Т, и, V, IV (с индексами), пустое слово обозначаем через Л.
2. Кроме конечных частичных слов, мы будем рассматривать также бесконечные частичные слова. Частичное 2-слово (и-слово) над алфавитом А — это частичная функция 1У : Z —> А (соответственно, И7: N->4).
3. Через ІДИ7) обозначим область определения частичной функции И7(г). Каждому частичному слову И7 над алфавитом А мы можем поставить в соответствие обычное слово У0 над расширенным алфавитом А0 = А и {о} следующим образом:
Отображение IV —* И 70 является биекцией. В дальнейшем под частичным словом мы будем понимать именно последовательность символов над алфавитом А и {о}.
Заметим, что роль символа о существенно отличается от роли остальных алфавитных символов. Его значение таково: «на этой позиции должен находиться алфавитный символ, неизвестно какой». В [6] символ о назывался дырой. Мы используем термин джокер, который кажется нам более уместным. Отличные от джокера символы алфавита, будем, как обычно, называть буквами.

р + д
(а - 2)
{да + у)д да + (д + 7 - 2)
(а - 2)
ад-дда2 + (7 - 2д)а - 27 (Зд - 2)а +
да + (д + 7 - 2) да + (д + 7 - 2) (Зд ~ 2) (д + 7 - 2)
= Зд - 2 - . .
да + (д + 7 - 2)
Знаменатель последней дроби положителен, числитель приводится к виду Зд2 + (7-8)д-27 + 4 с корнями дх = (2 — 7)/3, д2 = 2. Снова при всех допустимых значениях д дробь положительна, откуда
А(/9(р+д-2)+а-2,р, д) < Зд - 2 < 4(д - 1).
(1.4)
Теперь возьмём произвольное к = /3(р + д — 2) + к', к' < (р + д — 2). Докажем, что А(к,р, д) < 4(д — 1). Если к'+2 < р/д, положим а = &'+2, у = р — ад и применим случай 3, получая неравенство (1.4).
Пусть к'+2 > р/д. Предположим, что найдётся такое а, что к1 +
а +
Тогда, положив ю
и 7 = — ад. мы можем применить
случай 1 и вывести неравенство (1.2).
Предположим теперь, что указанного выше значения а не существует. Поскольку значения выражения а +
с ростом а на единицу увеличивается не более, чем на 2, то существует такое а, что
а +
*+1) + [
^1=*Чз,
V I
= С + 5.

(а+1)д1 р I
(1.5)
(1.6)
Положим 'Ш
и 7 = адр—ад и убедимся в применимости случая 2. В самом деле, если ги = |"^| =1, получаем к'+2 = а <р/д, противоречие;
откуда 7 < д.
(«+!)
отсюда ги > 2. Из (1.5) и (1.6) следует, что Итак, случай 2 применим. Получаем неравенство (1.3).
Теперь докажем, что шах(Д(А;,р, д)) > 2д. Пусть к — р(р+д—2). Из предложения 1.2 получаем Ь(к, р, д) = (Зрд + 2д и А(к, р, д) = /Зрд + 2д — Ррд = 2д.
Пункт 2). Произведём выкладки, аналогичные приведённым выше. Пусть р = ад + 1 и Д = 2ад. Тогда всякий д-класс встречается в хвосте ровно 2а раз, т.е. на шаге 2) построения специальной расстановки