авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

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

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

Гамзова Юлия Васильевна Комбинаторные свойства частичных слов 01.01.09 Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург, 2006

Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета им. А. М. Горького Научные руководители:

кандидат физико-математических наук, доцент А. М. Шур, кандидат физико-математических наук, доцент Е. В. Суханов

Официальные оппоненты:

доктор физико-математических наук, профессор А. В. Рожков, кандидат физико-математических наук, ст.н.с. А. Э. Фрид

Ведущая организация:

Санкт-Петербургское отделение математического института им. В. А. Стеклова Российской академии наук

Защита диссертации состоится 20 декабря 2006 года в 14 часов на за седании диссертационного совета К 004.006.01 по защите диссертаций на соискание ученой степени кандидата наук в Институте математи ки и механики УрО РАН по адресу: 620219,г.Екатеринбург, ГСП-384, ул.Софьи Ковалевской,16.

С диссертацией можно ознакомиться в библиотеке Института мате матики и механики УрО РАН.

Автореферат разослан 16 ноября 2006 г.

Ученый секретарь диссертационного совета К 004.006. кандидат физико-математических наук, ст.н.с. Скарин В. Д.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертация посвящена исследованию свойства взаимодействия периодов для периодических и локально периодических частичных слов.

Актуальность темы. Символьные последовательности, или сло ва, представляют собой важный и популярный объект комбинатор ных исследований. Соответствующие задачи возникают в алгебре, динамике, многих разделах компьютерных наук, молекулярной био логии, биоинформатике. Историю комбинаторики слов принято от считывать от 1906 года, когда была опубликована работа А. Туэ [1].

С тех пор комбинаторика слов плодотворно развивалась и к насто ящему времени обрела четкие контуры и собственную богатую про блематику. Имеющаяся литература весьма обширна. Упомянем здесь монографии [2–4], а также [5] и ряд других глав трехтомного Спра вочника по формальным языкам.

Частичные слова представляют собой естественное обобщение по нятия обычного слова. Частичное слово длины n над алфавитом A это частичная функция W : {1,..., n} A с областью определе ния D(W ), обычно представляемая в виде слова над расширенным алфавитом A {};

символ, подставляемый вместо неопределен ных букв в W, называется джокером. Частичное Z-слово это ча стичная функция W : Z A. Частичное слово является моделью для любой линейной информации, часть которой недоступна или не важна;

в частности, частичные слова используются для моделирова ния различных биологических последовательностей. Изучение ком бинаторных свойств частичных слов в явном виде началось совсем недавно, в 1999 году, с работы Ж. Берстеля и Л. Буассона [6]. В по следнее время комбинаторика частичных слов интенсивно развива ется. Отметим работы Ф. Бланше-Садри, П. Лёйпольда, Г. Лишке, В. Халавы, Т. Харью, Т. Карки.

Большинство постановок задач для частичных слов представляет собой рассмотрение естественных аналогов свойств обычных слов в классе частичных слов. Богатую проблематику для исследований по частичным словам предоставляет одно из ключевых свойств обыч ных периодических слов свойство взаимодействия периодов. Это свойство (в стандартной формулировке) заключается в том, что достаточно длинное слово с периодами p и q имеет также и произ водный период НОД(p, q). Точная формулировка для обычных слов содержится в следующей теореме.

Теорема (Файн, Вильф, [7]). Пусть p и q – натуральные числа, тогда каждое слово длины не менее, чем p+qНОД(p, q) с периодами p и q имеет период НОД(p, q).

Свойство взаимодействия периодов и различные его обобщения рассматривались в работах Д. Джиаммарези, С. Мантацци, Ф. Ми ньози, А. Рестиво, П. Сильвы, Д. Рамартера, Р. Тийдельмана, С. Кон стантинеску, Л. Илие и ряда других авторов.

Для частичных слов выполнение свойства взаимодействия перио дов зависит не только от длины слова, но и от количества и располо жения в нем джокеров, а также от того, какое из двух естественных обобщений понятия периода используется: частичное слово W имеет - период p, если i, j D(W ) (i j(modp)) (W (i) = W (j));

- локальный период p, если iD(W ) (i+pD(W )) (W (i)=W (i+p)).

Таким образом, возникает несколько нетривиальных постановок задач. Вначале сформулируем задачи для периодов.

1. Для произвольных фиксированных p, q, k выяснить, в каких ча стичных словах с k джокерами взаимодействуют периоды p и q.

В дальнейшем будет показано, что периоды взаимодействуют в любом частичном слове достаточно большой длины (ранее для k = такой результат был получен в [6]). Таким образом, для произволь ных натуральных p, q, k можно указать длину L такую, что любое частичное слово длины не менее L, имеющее периоды p, q и содержа щее k джокеров, обязательно имеет период НОД(p, q). Наименьшую такую длину будем называть длиной взаимодействия периодов p и q при наличии k джокеров и обозначать L(k, p, q). Естественным раз витием задачи 1 является следующая задача.

2. Для произвольных фиксированных p, q, k оценить длину взаимо действия L(k, p, q).



Единственным известным результатом по данной задаче является равенство L(1, p, q) = p + q ([6]).

Следующий результат показывает целесообразность рассмотре ния обобщений свойства взаимодействия периодов.

Теорема ([5]). Если (обычное) слово U имеет взаимно простые пе риоды p q и |U| = p + q r, где 1 r q, то U содержит не более r различных букв.

Скажем, что для слова U выполняется обобщенное свойство вза имодействия периодов, если некоторое ограничение, накладываемое на U парой периодов (p, q), сильнее совокупности ограничений, на кладываемых на U периодами p и q по отдельности. В приведенной выше теореме таким ограничением является ограничение на количе ство различных букв в U.





Наряду с задачами 1 и 2 будем рассматривать следующую задачу.

3. Исследовать обобщенное свойство взаимодействия периодов для частичных слов.

Теперь перейдем к задачам для локальных периодов.

1Л. Для произвольных фиксированных p, q, k выяснить, в каких ча стичных словах с k джокерами взаимодействуют локальные пери оды p и q.

В отличие от случая периодов, фиксированные локальные пери оды могут не взаимодействовать в сколь угодно длинном частич ном слове даже при k = 2 ([6]). В статье [8] доказано, что свойство взаимодействия периодов выполняется только для локально перио дических частичных слов, не содержащих подпоследовательностей особого вида. Следуя [8], будем называть специальными конечные подпоследовательности позиций джокеров, наличие которых приво дит к невыполнению свойства взаимодействия локальных периодов во всем слове. В бесконечном частичном слове вероятность наличия специальных подпоследовательностей равна единице, если джокер с равной ненулевой вероятностью может находиться в любой позиции.

Тем самым, для завершения решения задачи 1Л необходимо дать си стематическое описание специальных подпоследовательностей.

Для произвольных натуральных p, q, k можно указать длину L та кую, что любое частичное слово длины не менее L без специальных подпоследовательностей, имеющее локальные периоды p, q и содер жащее k джокеров, обязательно имеет период НОД(p, q). Наимень шую такую длину будем называть длиной взаимодействия локаль ных периодов p и q при наличии k джокеров и обозначать L (k, p, q).

2Л. Для произвольных фиксированных p, q, k оценить длину взаимо действия L (k, p, q).

Решение этой задачи приведено в [8].

Теорема (Бланше-Садри, [8]). Пусть k, p, q - натуральные числа, НОД(p, q) = 1. Тогда L (k, p, q) = (k/2 + 1)(p + q) (k + 1) mod 2.

Как и для периодичности, для локальной периодичности мож но рассматривать обобщенное взаимодействие периодов в частичных словах, для которых не выполняется свойство взаимодействия пери одов в стандартной формулировке. Сформулируем соответствую щую задачу.

3Л. Исследовать обобщенное свойство взаимодействия локальных периодов частичных слов.

Целью работы является исследование свойства взаимодействия периодов для периодических и локально периодических частичных слов в рамках сформулированных выше задач 1-3, 1Л, 3Л.

Методы исследования. Основную роль играют методы комби наторики слов и теории графов. Кроме того, используются класси ческая комбинаторика, динамическое программирование.

Научная новизна. Все результаты диссертации являются новы ми.

Теоретическая и практическая ценность. Диссертационная работа носит теоретический характер. Полученные результаты мо гут быть применены в теории формальных языков и комбинаторике слов, а также использованы при чтении специальных курсов по дис кретной математике.

Апробация работы. Результаты диссертации докладывались на международных конференциях Mathematical Foundations of Com puter Science (Марианские Лазни, Чехия, 2001), WORDS’03 (Тур ку, Финляндия, 2003), российской конференции Дискретный анализ и исследование операций (Новосибирск, 2004), Международной ал гебраической конференции, посвященной 100-летию со дня рождения П. Г. Конторовича и 70-летию Л. Н. Шеврина (Екатеринбург, 2005) и научных семинарах Алгебраические системы (УрГУ) и Дискрет ная математика (УрГУ).

Публикации. Основные результаты диссертации опубликованы в 8 работах, список которых приводится в конце автореферата. В совместных работах [9–12] руководителю принадлежат постановка задачи и общая методика исследований, доказательства всех основ ных утверждений принадлежат автору.

Структура и объем работы. Диссертация состоит из введения, трех глав, разделенных на 13 параграфов, и содержит 5 теорем. Об щий объем диссертации составляет 98 страниц. Библиографический список содержит 45 наименований. Нумерация параграфов сквозная;

в нумерации утверждений используются номера глав.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении приводится обзор литературы по исследуемой про блематике, определяется цель работы, излагаются основные резуль таты и содержание работы.

В первой главе диссертации приводится решение задач 1 и 2.

Как отмечалось в разных работах (см. [5,6]), утверждения о взаимо действии произвольных периодов p и q тривиально следуют из ана логичных утверждений для взаимно простых периодов ввиду следу ющего наблюдения.

Наблюдение. В случае, когда НОД(p, q) = d 1, можно заменить (частичное) слово U набором из d (частичных) слов U1,..., Ud, где Ui = U(i)U(d+i)U(2d+i).... Каждое из этих слов будет иметь взаим но простые периоды p/d, q/d. При этом слово U будет иметь период d тогда и только тогда, когда все Ui имеют период 1.

Таким образом, достаточно исследовать свойство взаимодействия для взаимно простых периодов. В этом случае свойство взаимодей ствия периодов заключается в том, что в достаточно длинном слове с периодами p и q все буквы должны быть одинаковыми. В дальнейшем мы рассматриваем только взаимно простые периоды и предполага ем, что 2 q p.

В первом параграфе мы доказываем, что длина взаимодействия L(k, p, q) существует для любых периодов p и q и количества джоке ров k и получаем для длины взаимодействия следующую оценку.

Теорема 1.1. Для любых взаимно простых p q 2 и любого k L(k, p, q) p + (k + 1)q 1.

Равенство достигается в двух случаях: когда k = 0 и когда q = 2 и p делит k.

Во втором параграфе мы уточняем оценку для длины взаимодей ствия из теоремы 1.1 в двух частных случаях: q = 2 и k = 2.

Теорема 1.2. Для любого нечетного p и любого k L(k, p, 2) = (2k/p + 1)p + k mod p + 1.

Теорема 1.3. Для любых взаимно простых p q L(2, p, q) = p + 2q 1.

При более пристальном изучении длины взаимодействия L(k, p, q) как функции от k с параметрами p и q можно заметить, что она име ет, за исключением некоторого начального отрезка, регулярное по ведение. Если отбросить рассмотренный в теореме 1.2 случай q = и случай маленьких k, то можно значительно улучшить оценку для длины взаимодействия из теоремы 1.1 в общем случае. В следующей теореме, являющейся центральным результатом главы 1, эта длина представлена в виде суммы линейной и периодической функций от носительно k. Такое представление позволяет получить максимально точную общую (т.е. пригодную для любых p и q) оценку длины взаимодействия.

Теорема 1.4. Пусть p и q взаимно простые натуральные числа, p q 3, а натуральное число k таково, что k 2p/31 при q= и k 3p/q+3 при q4. Пусть L(k, p, q) длина взаимодействия периодов p и q при наличии k джокеров. Тогда pq L(k, p, q) = · k + (k, p, q), p+q где функция (k, p, q) является периодической по k с периодом p + q 2 и удовлетворяет следующим условиям:

1. для произвольных p и q 2q max((k, p, q)) 4(q 1);

2. для любого 0 и произвольного q существует p такое, что max((k, p, q)) 4(q 1) 3. для произвольных p и q pq min((k, p, q)) =.

p+q Следствие 1.1. В условиях теоремы 1.4 длина взаимодействия удо влетворяет неравенству pq L(k, p, q) · k + 4(q 1).

p+q Функция, стоящая в правой части неравенства, является наилуч шей верхней оценкой для L(k, p, q) в классе линейных по k функций с параметрами p и q.

Результаты теорем 1.1 и 1.4 дополняют друг друга. Верхняя оцен ка для длины взаимодействия теоремы 1.1 применима при любом количестве джокеров k 0 и любых значениях периодов. Оценка теоремы 1.4 применима с некоторыми ограничениями, но она суще ственно точнее, является двусторонней, и позволяет локализовать длину взаимодействия внутри полосы, ширина которой меньше 4q.

Полученные результаты позволяют провести интересное сравне ние свойств локальной и глобальной периодичности с точки зрения свойства взаимодействия периодов. В отличие от глобальной перио дичности, для локальных периодов в общем случае нельзя указать оценку для длины взаимодействия. Для того, чтобы можно было оценить длину взаимодействия, необходимо рассматривать только те расстановки, в которых размещение пропущенных символов удовле творяет некоторому достаточно обременительному ограничению. Из теоремы Бланше-Садри следует, что в этом случае взаимодействие локальных периодов гарантировано, если доля пропущенных сим волов в слове не превосходит величину 2/(p + q), т.е. обратно про порциональна большему периоду. В то же время, оценка теоремы 1.4 показывает, что допустимая (для гарантированного взаимодей ствия периодов) доля пропущенных символов в периодическом ча стичном слове может быть существенно большей;

а именно, величина k/L (p + q 2)/pq обратно пропорциональна меньшему периоду.

Параграфы с третьего по пятый посвящены доказательству тео ремы 1.4. Для этого сформулирована обратная задача: задана длина слова L и его периоды p, q, необходимо найти минимальное количе ство джокеров, при котором слово может не иметь периода 1. Для обратной задачи приводится конструктивное решение, т.е. указыва ется способ расстановки джокеров в слове, доставляющий искомый минимум.

Во второй главе рассматривается задача 3 для периодических частичных слов, длина которых меньше длины взаимодействия. Ис пользуется тот же вариант обобщенного свойства взаимодействия пе риодов, что и для обычных слов: количество различных букв в ча стичном слове ограничено константой, меньшей q. Для уточнения постановки задачи введем необходимые определения.

Для данного частичного слова W рассмотрим множество частич ных слов с теми же периодами и той же областью определения. Среди этих слов выберем слово U с максимальным количеством различных букв. Множество всех позиций слова U, содержащих одну и ту же букву, будем называть доменом W. Количество доменов слова W (т.е. количество различных букв в U) назовем размерностью слова W и обозначим через r(W ). Из определений следует, что количество букв в частичном слове не превышает его размерности, а две позиции могут содержать различные буквы только если эти позиции принад лежат разным доменам. Таким образом, периоды p и q обобщенно взаимодействуют в W, если размерность W меньше q.

Поскольку размерность и множество доменов частичных слов определяются только периодами и областью определения, мы вме сто частичных слов рассматриваем расстановки. Расстановка R это слово над алфавитом {0, 1}, полученное из частичного слова W по правилу 1, i D(W ) R(i) = 0, i D(W ).

/ Все частичные слова, которым соответствует данная расстановка R, имеют одинаковую размерность и множество доменов, поэтому мы будем говорить о множестве доменов и размерности расстановки.

Заметим, что расстановки одинаковой длины с одинаковым количе ством джокеров могут иметь различную размерность.

Во второй главе даются ответы на следующие вопросы:

1. Чем определяется размерность расстановки?

2. Для фиксированных p и q, как вычислить величину P (r, L, k), равную доле расстановок данной размерности r среди всех рас становок длины L с k джокерами и периодами p, q?

В шестом параграфе показано, что размерность произвольной расстановки R совпадает с размерностью эффективно вычислимой расстановки длины pq, называемой характеристической расстанов кой для R. На основании этого утверждения предложена схема ал горитма для вычисления P (r, L, k).

В седьмом параграфе решена задача вычисления мощности клас са расстановок (имеющих заданную длину L, количество джокеров k и размерность r), определяемого данной характеристической рас становкой.

В восьмом параграфе приведено описание алгоритма для вы числения P (r, L, k). Вначале вычисляются вспомогательные таблицы (время выполнения этого этапа полиномиально зависит от L и p и экспоненциально от параметра q), а затем по формуле вычисляет ся P (r, L, k) (время выполнения этого этапа полиномиально зависит от L, p и q). Заметим, что время работы наивного алгоритма вы числения P (r, L, k) экспоненциально зависит от длины слова, так что выигрыш во времени при использовании предложенного алгоритма очень значителен.

В девятом параграфе приводятся и анализируются результаты, полученные с помощью программы, реализующей данный алгоритм.

Третья глава посвящена исследованию свойства взаимодей ствия локальных периодов частичных слов (задачи 1Л, 3Л). Иссле дования проводятся для Z-слов, но все результаты легко переносятся и на случай конечных слов.

Локальная периодичность накладывает на слово гораздо более слабые ограничения, чем глобальная. В частности, наличие у слова локального периода p не ограничивает размерность слова. Поэтому для локально периодических частичных слов имеет смысл рассмат ривать в качестве обобщенного свойства взаимодействия локальных периодов выполнение некоторых условий для множества доменов.

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

1. Какой вид имеют специальные подпоследовательности?

2. Каковы необходимые и достаточные условия наличия в слове специальных подпоследовательностей?

3. В каком случае частичное Z-слово содержит хотя бы один бес конечный домен?

4. В каком случае частичное Z-слово содержит только бесконеч ные домены?

В десятом параграфе описывается используемая техника, осно ванная на сопоставлении частичному Z-слову с периодами p, q беско нечного графа, называемого графом локальной периодичности. Этот граф можно изобразить двумя системами спиралей на бесконечном цилиндре. Множество доменов частичного слова совпадает с множе ством компонент связности данного графа.

В одиннадцатом параграфе доказываются некоторые свойства специальных конечных подпоследовательностей, а также приводит ся классификация минимальных по включению таких подпоследова тельностей.

В двенадцатом параграфе описан алгоритм проверки наличия в частичном слове специальной подпоследовательности. Алгоритм просматривает позиции джокеров частичного слова в определенном порядке и обнаруживает позицию, гарантированно принадлежащую специальной подпоследовательности, если хотя бы одна такая подпо следовательность имеется. Об эффективности алгоритма доказана следующая теорема.

Теорема 3.1. Время работы алгоритма проверки наличия в ча стичном слове специальных подпоследовательностей линейно зави сит от длины исследуемого слова. Используемый объем памяти ли нейно зависит от периодов p, q.

В тринадцатом параграфе приводятся две модификации описан ного алгоритма. Первая из них позволяет определить количество до менов в конечном частичном слове. Вторая модификация алгорит ма предназначена для поиска специальных подпоследовательностей определенного типа, ответственных за бесконечные домены в ча стичных Z-словах.

Таковы основные результаты диссертации.

Работа выполнена под руководством доцента Арсения Михайло вича Шура и доцента Евгения Витальевича Суханова, которым автор выражает глубокую благодарность за постоянное внимание и всесто роннюю поддержку.

ЗАКЛЮЧЕНИЕ Диссертационная работа посвящена изучению свойства взаимо действия периодов для частичных слов.

Получены следующие основные результаты:

1. Доказана теорема о существовании длины взаимодействия пе риодов для частичных слов, получена оценка длины взаимо действия. Получены точные оценки длины взаимодействия в двух частных случаях (q = 2 и k = 2) и максимально точная общая (т.е. пригодная для любых периодов p, q) оценка длины взаимодействия, применимая при некоторых ограничениях на количество джокеров.

2. Построен алгоритм вычисления доли расстановок длины L, со держащих k джокеров и имеющих размерность r. Время работы этого алгоритма полиномиально зависит от L и p и экспонен циально от параметра q.

3. Дана классификация специальных подпоследовательностей. По строен алгоритм проверки наличия в слове специальных под последовательностей. Время работы этого алгоритма линейно зависит от L, используемая память линейно зависит от пара метров p, q. Также предложена модификация алгоритма, поз воляющая находить специальныe подпоследовательности опре деленного типа.

Литература [1] Thue A. Uber unendliche Zeichenreihen // Norske Vid. Selsk. Skr.

I Math-Nat. Kl. 1906. Vol. 7. Pp. 1–22.

[2] Lothaire M. Combinatorics on Words. Addison-Wesley, 1983.

[3] Lothaire M. Algebraic combinatorics on Words. Cambridge University Press, 2002.

[4] Lothaire M. Applied combinatorics on Words. Cambridge University Press, 2005.

[5] Chorut C., Karhumki J. Combinatorics of words // Handbook of a formal languages / Ed. by G.Rozenberg, A.Salomaa. Springer, Berlin, 1997. Vol. 1.

[6] Berstel J., Boasson L. Partial words and a theorem of Fine and Wilf // Theor. Comp. Sci. 1999. Vol. 218. Pp. 135–141.

[7] Fine N., Wilf H. Uniqueness theorem for periodic functions // Proc.

Amer. Math. Soc. 1965. Vol. 16. Pp. 109–114.

[8] Blanchet-Sadri F. Periodicity on partial words // Comput. Math.

Appl. 2004. Vol. 47. Pp. 71–82.

Публикации по теме диссертации [9] Shur A. M., Konovalova Yu. V. On the periods of partial words // Lect. Notes Comp. Sci. 2001. Vol. 2136. Pp. 657–665.

[10] Коновалова Ю. В., Шур А. M. Периодические частичные сло ва // Российская конф.“Дискретный анализ и исследование опе раций”: Тез. докл. Новосибирск, Институт математики СО РАН, 2002. P. 130.

[11] Shur A. M., Gamzova Yu. V. Periods’ interaction property for partial words // Proceedings of WORDS’03, 4th International Conference on Combinatorics on Words. 2003. Pp. 75–82.

[12] Шур А. M., Гамзова Ю. В. Частичные слова и свойство взаимо действия периодов // Изв. РАН. Cерия матем. 2004. Т. 68, № 2. С. 199–222.

[13] Гамзова Ю. В. Статистические закономерности взаимодействия периодов частичных слов // Российская конф.“Дискретный ана лиз и исследование операций”: Тез. докл. Новосибирск, Инсти тут математики СО РАН, 2004. С. 82.

[14] Гамзова Ю. В. Статистические закономерности взаимодействия периодов частичных слов // Дискретный анализ и исследование операций. Серия 1. 2004. Т. 11, № 4. С. 20–35.

[15] Gamzova Yu. V. Innite walks on the set of integers with gaps // Международная алгебраическая конф.: Тез.докл. Екатерин бург, УрГУ, 2005. С. 195–196.

[16] Гамзова Ю. В. Локально периодические бесконечные частичные слова // Изв.УрГУ. Серия компьютерные науки и информаци онные технологии, вып.1. 2006. Т. 43. С. 5–21.

До 2002 г. автор носила фамилию Коновалова.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.