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

Оглавление
Введение 3
1°. Понятие о частичных словах................................ 3
2°. Определения и обозначения ................................ 4
3°. Краткий обзор исследований по частичным словам 5
4°. Вопросы, рассматриваемые в диссертации.................... 8
5°. Основные результаты диссертации ......................... 13
I Свойство взаимодействия периодов 19
§1 Существование длины взаимодействия....................... 19
§2 Точные оценки в частных случаях...........................25
§3 Формулировка прямой и обратной задачи. Бланки и расстановки ..................................................... 27
§4 Решение обратной задачи...................................32
§5 Решение исходной задачи...................................46
II Статистические закономерности 53
§6 Идея алгоритма............................................53
§7 Количество расстановок с заданной характеристической расстановкой .................................................... 55
§8 Построение вспомогательных таблиц.........................58
§9 Анализ полученных результатов.............................63
III Свойство взаимодействия локальных периодов 66
§10 Используемая техника......................................66
§11 Разрезы...................................................71
§12 Алгоритм проверки наличия в расстановке специальной
подпоследовательности.....................................84
§13 Модификации алгоритма.....................................87
2
Введение
1°. Понятие о частичных словах
Символьные последовательности, или слова, представляют собой важный и популярный объект комбинаторных исследований. Задачи, связанные со словами, возникали в различных областях математики и других наук и привели к возникновению отдельного раздела дискретной математики, занимающейся изучением комбинаторных свойств слов. Историю комбинаторики слов принято отсчитывать от 1906 года, когда была опубликована работа [1]. С тех пор комбинаторика слов плодотворно развивалась и к настоящему времени обрела четкие контуры и собственную богатую проблематику. Имеющаяся литература весьма обширна. Упомянем здесь монографии [2-4], а также [5] и ряд других глав трехтомного «Справочника по формальным языкам».
Частичные слова представляют собой естественное обобщение понятия обычного слова. Частичное слово — это обычное слово, в котором часть букв по каким-то причинам отсутствует. Изучение комбинаторных свойств частичных слов «в явном виде» началось совсем недавно, в 1999 году, с работы [6].
Задачи, в которых возникают частичные слова, можно разделить на два типа. В задачах первого типа некоторая часть информации нам не важна (вне зависимости от того, доступна она или нет). Примером может служить задача поиска в тексте по шаблону, когда шаблон содержит символ (или символы) со значением «что угодно». В задачах второго типа некоторая часть информации для нас важна, но по каким-либо причинам недоступна. По имеющейся части информации и некоторым дополнительным условиям необходимо полностью восстановить информацию. Примером является задача восстановления фрагментов файлов, повреждённых при передаче или в результате норчи носителя. Очень интересными представляются также задачи молекулярной биологии (см. [7]), в частности, задача реконструкции нуклеотидных цепочек ДНК по частично расшифрованным фрагментам.
3
В данной работе изучаются комбинаторные свойства частичных слов, связанные с локальной и глобальной периодичностью.
2°. Определения и обозначения
1. Пусть А — конечный алфавит, А+ и А* — соответственно свободная полугруппа и свободный моноид над этим алфавитом. Элементы из А+ и А* называются словами, а множества слов — языками. Длина слова W обозначается через \W\. Для данной буквы а Є А обозначим через \и\а количество букв а в слове U. На слово длины п можно смотреть как на функцию из множества {1,... ,п} в алфавит. Частичное слово длины п над алфавитом А — это частичная функция
W : —> Л.
Значение \V(i) мы будем называть буквой в і-ой позиции слова W. Слова (обычные и частичные) мы обозначаем буквами Р, Q, R, 5, Т, U, V, W (с индексами), пустое слово обозначаем через Л.
2. Кроме конечных частичных слов, мы будем рассматривать также бесконечные частичные слова. Частичное Z-слово (и-слово) над алфавитом А — это частичная функция W : Z —* А (соответственно, W:N->A).
3. Через D(W) обозначим область определения частичной функции W(i). Каждому частичному слову W над алфавитом А мы можем поставить в соответствие обычное слово W0 над расширенным алфавитом А0 = A U {о} следующим образом:
_ Г W(i), і Є D(W) ly°W \ о, iiD(W).
Отображение W —> W0 является биекцией. В дальнейшем под частичным словом мы будем понимать именно последовательность символов над алфавитом A U {о}.
Заметим, что роль символа о существенно отличается от роли остальных алфавитных символов. Его значение таково: «на этой позиции должен находиться алфавитный символ, неизвестно какой». В [6] символ о назывался дырой. Мы используем термин джокер, который кажется нам более уместным. Отличные от джокера символы алфавита, будем, как обычно, называть буквами.
4
4. Обычное слово \У имеет период р, если И'(г) = И7(г + р) доя всех і = 1,..., \ \У\ - р. Понятие периода можно распространить на частичные слова двумя естественными способами, предложенными в [6]. Приведём соответствующие определения.
Частичное слово \V имеет период р, если для любых і,у є 0(\¥) і = Дтосір) => И7(г) = \¥(у).
Например, слово И7 = аЬоаосаЬс имеет период 3.
Частичное слово IV имеет локальный период р, если для любого і такого, что г, г + р Є ІДИ7), выполняется W{г) = IV(і + р). Для обычных слов наличие локального периода р всегда влечет наличие периода р, но это свойство не выполняется для частичных слов. Например, частичное слово IV = аЬсоЬЫ имеет локальный период 3, но не имеет периода 3. Заметим, что частичное слово имеет период р тогда и только тогда, когда в нём все джокеры можно заменить буквами так, что полученное обычное слово будет иметь период р.
5. Слово V называется подсловом слова \У (или говорят, что № содержит К, обозначается V < И7), если IV = РУС} доя некоторых слов Р, С). При этом мы говорим, что V является
♦ префиксом И7, если Р = Л;
• суффиксом И7, если (} = \.
Если V — подслово И7, начинающееся в г-й и заканчивающееся в 7-й позиции, то используется запись V =
Любое представление слова в виде произведения подслов мы называем разбиением этого слова.
6. Будем обозначать через [п\ нижнее целое, через \п] — верхнее целое числа п.
3°. Краткий обзор исследований по частичным словам
С момента возникновения комбинаторики частичных слов исследования по частичным словам велись довольно интенсивно и уже получено много интересных результатов. Комбинаторика частичных слов находится
в начальной фазе развития, когда основной интерес представляет перенесение комбинаторных свойств обычных слов на более широкий класс частичных слов. Уже в [б] были получены для частичных слов аналоги некоторых комбинаторных свойств обычных слов. В частности, рассматривалось в частных случаях свойство взаимодействия периодов частичных слов. Исследование этого свойства продолжалось и в других работах. Свойство взаимодействия периодов тесно связано с нашими исследованиями; оно будет рассмотрено в следующем параграфе.
Рассматривались и другие свойства периодических частичных слов. В частности, в [8] проводились исследования аналога теоремы о критическом разбиении. Введем необходимые определения. Число р Е N называется локальным периодом (обычного) слова Н7 в позиции к, 0 < к < \ХУ\, если слово И^(п1...П2) имеет период р, где щ = тах{А; - р + 1,1}, П2 = пип {А: + р, |И^|}. Смысл понятия локального периода таков: в р-окрестности позиции к слово XV ведет себя как периодическое с периодом Р-
Разбиение И7 = ЦУ называется крити'ьеским, если минимальный локальный период слова XV в позиции \и\ совпадает с его минимальным периодом.
Теорема 0.1 (теорема о критическом разбиении, [9,10]). Всякое слово XV, имеющее минимальный период р и содержащее не мепее двух различных букв, допускает критическое разбиение XV = 1/У с условием \и\ < р.
Из доказательства этой теоремы следует эффективный алгоритм построения этого разбиения.
Введем для частичных слов понятие, аналогичное понятию локального периода для обычных слов. Число р Е N называется точечным периодом частичного слова XV в позиции к, 0 < к < \\У\, если слово XV(щ ... Пг) имеет период р, где щ = тах{£ - р + 1,1}, щ = тт{& + р, {XV\]. Заметим, что дня данного определения можно использовать любое из двух определений периода частичного слова, т.к. длина периодической части слишком мала для того, чтобы успели проявиться различия между локальной и глобальной периодичностью.
В [8] доказан «условный» аналог теоремы о критическом разбиении для частичных слов с одним джокером, т.е. выявлены необходимые и достаточные условия наличия в слове критическою разбиения. В [11] этот результат обобщен для частичных слов с любым количеством джокеров.
Также для частичных слов проводились исследования множества пе-
0
риодов. Обозначим через Т(и) множество периодов слова и. Для обычных слов известен следующий результат.
Теорема 0.2 ([12]). Для любого слова С/ над алфавитом Л существует слово V длины \Ц\ над алфавитом {0,1} такое, что Т>(У) = 'Р(Ц).
Доказательство этой теоремы, приведенное в [12], является довольно сложным. В [13] дается более простое конструктивное доказательство. Алгоритм из [13] был обобщен в [14] для частичных слов с одним джокером, в [15] — с двумя джокерами, в [16] — с произвольным количеством джокеров.
Также изучались свойства примитивных частичных слов. Будем говорить, что частичное слово и содержится в частичном слове V (и С V), если \Ц\ = \У\, 0(11) С 0(У) и и({) = У(г) для всех г 6 0(11). Частичные слова II и V называются совместимыми (и Т У)> если существует слово IV, в котором содержатся и слово Ц, и слово V. Обычное слово и называется примитивным, если не существует слова V такого, что Ц = Кп,п > 2. Частичное слово II называется примитивным, если не существует слова V такого, что и С Уп,п > 2. В [17] приведены для примитивных частичных слов аналоги известных свойств примитивных обычных слов. В [18] приведен для частичных слов аналог известного критерия примитивности обычных слов, позволяющий создать линейный по времени алгоритм проверки примитивности частичного слова.
Большой интерес представляет изучение множеств частичных слов (ч-языков). В 2004 году Ф. Блашнс-Садри сделала первый шаг в изучении свойств ч-языков, введя понятие ч-кодов в статье [19].
Напомним, что непустое множество слов X 6 называется кодом, если для всех натуральных га, п и слов ..., £/т, У\,..., Уп € X выполняется
(и,и2'..ит = УУ2...Уп)^(т = п)Ь(и{ = У>),{ = \,...,т
Непустое множество частичных слов X € А+ называется ч-кодом} если для всех натуральных т,пи частичных слов Ц\,..., С/т, Ц,..., Уп € X выполняется
(ихи2... ит Т УгУ2... Уп) =* (т = п) Л (I/,-= И), * =1,...,т
В [19] приведены различные свойства ч-кодов. В [20] приводится алгоритм для проверки, является ли данный ч-язык ч-кодом.
П. Лёйпольд в статье [21] предложил несколько способов получения ч-языков, а также привел некоторые свойства этих языков.
7