Восстановление и различимость слов по подсловам тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Хошманд Асл Мохаммад Реза

Восстановление и различимость слов по подсловам

Специальность 01.01.09 - дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2005

Работа выполнена на кафедре математических методов прогнозирования факультета Вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Научный руководитель: доктор физико-математических наук,

Профессор В. К. Леонтьев Официальные оппоненты: доктор физико-математических наук,

Ю.Г. Сметания,

кандидат физико-математических наук, М.Н. Вялый

Ведущая организация: Институт системного программирования Российский

Академии наук.

Защита диссертации состоится "15" декабря 2005 в 13 ч. 00 мин. на заседании диссертационного совета Д 002.017.02 при Вычислительном центре им. A.A. Дородницына РАН по адресу: 119991, г. Москва, ул. Вавилова, дом 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН.

Автореферат разослан "_"_- 2005.

Ученый секретарь диссертационного совета Д 002.017.02 при ВЦ РАН доктор физико-математических наук

Рязанов В. В.

Общая характеристика работы

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

Одной из известных моделей при такого рода исследованиях является модель реконструкции слова по его частям. При этом 'Часть" слова определяется исходя из содержательных соображений. Одними из широко употребительных частей слова являются "подслово" и "фрагмент".

При этом логика задачи может диктовать условия: рассматривать "части" с учётом их кратности или без этого условия. Математические задачи, которые при этом возникают, существенно различаются между собой. В обоих случаях основная задача состоит в характеризации всех слов фиксированной длины имеющих данный "набор" частей. Так вводится понятие эквивалентности слов и разбиение всего множества слов длины п на классы эквивалентности. Каждый класс эквивалентности содержащий единственное слово, полностью его определяет. Возникает проблема о минимальной "длине" частей определяющей однозначно любое слово.

В диссертации рассматривается задачи реконструкции и различимости слов по их под-словам.

Целью работы является

1. Описание классов эквивалентности слов по подсловам на языке дизъюнктивных нор-

мальных форм (Д.Н.Ф.).

2. Построение алгоритмов для выяснения эквивалентности пар слов из В".

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

слова и построение алгоритмов реконструкции.

4. Построение тестов для различения слов фиксированной длины и нахождение оценок

длин тестовых слов.

Научная новизна.

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

Методика исследования. Методы комбинаторного анализа.

Практическая ценность. Предложенные в диссертации алгоритмы позволяют реконструировать и различать двоичные слова длины < 10s за приемлемое время.

Апробация работы. Материалы, изложенные в диссертации докладывались на

- Российской конференции "Дискретный анализ и исследование операций"(Новосибирск,

2004 г.)

- Международного семинара "Дискретный математика и ее приложения"(Москва, 2004

г.)

- Международного конференции "36th Annual iranian mathematics conference"(HpaH, Яз-

ды 2005)

По теме диссертации опубликовано трех работы.

Объем и структура работы. Диссертация состоит из введения, 2-х глав и списка литературы. Общий объем 67 страниц.

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

Глава I. Введение.

Часть и целое всегда является предметом изучения иаукя. Основной философский вопрос при таком изучении звучит так: как устроен мир? Если при исследовании информацию принят следующий тезис:

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

Глава II.

Основным объектом изучения в диссертации являются слова конечной длины над бинарным алфавитом {0,1}. Это множество обозначается через В*. Если х = Х1Х2 ■ • -хп-слово из В", то любое слово вида ХкХк+1 ■ ■ ■ хк+т называется подсловом х. При этом 1 < к < п — г. Таким образом множество всех подслов длины к слова х содержит не более чем (п — к + 1)— различных подслов и общее число подслов слова длины п с учётом их кратности, равно (п£1). Каждое подслово а слова х несёт определённую информацию об этом слове. Как оценить или измерить эту информацию? Этот вопрос является одним из ключевых вопросов, рассматриваемых в этой диссертации. Интуитивно ясно, что чем длиннее подслова слова х, тем больше несут они информации об исходном слове. В каком случае слово можно однозначно восстановить по набору его подслов ограниченной длины и в каком случае это можно сделать лишь с определенной погрешностью? Все эти вопросы уже рассматривались в целом ряде исследований, относящихся к комбинаторике слов и на многие из них получены ответы той или иной степени полноты и определённости. Однако вопросы восстановимое™ и различимости формулировались в основном по отношению к фрагментам слова, а не к подсловам.

Фрагмент- это более широкое понятие частя слова, чем только подслова ограниченной длины Однако подслово- это более структурированная часть слова, чем фрагмент, что также привносит определённую специфику в проблему восстановимости и различимости по подсловам. Бели х = (xii2 • • • х„) € В*, то длину слова х мы будем обозначать через \х\. Множество всех бинарных слов длины п и < п мы будем обозначать соответственно через В" и В-п. Множество В* является моноидом с операцией конкатенации

х,у е В' -у ху € В*

Определение 1. Слово у — (у\уг ■ ■ - ук) называется полсловом слова х — (iii2 ■ • • хп). если

X, = У1,1.+1 = 2/2, • • ' , Xi+k-l = Ук для некоторого г из интервала [1,п — к + 1].

Слово у = (У1У2 ■ - -ук) называется фрагментом слова х = {xix2 ■ ■ ■ х„), если существует такая последовательность 1 < h < < ■ ■ ■ < ц < п, что

xi, =vl,xtl =îî2,'" ,x,t — y к

Замечание. У части авторов исследований по комбинаторике слов используется несколько отличная терминология. Так в монографии[1] подслово (subword) в нашей терминологии- это фактор (factor), а фрагмент- это подслово. Мы будем придерживаться введённых выше обозначений, понимая всю условность преимуществ и недостатков различных терминологий.

На множестве В* введём частичный порядок (<) , положив

х < у

если х— является подсловом слова у.

Пусть а € В и Vfc(a)— мультимножество всех подслов длины к у слова о. По другому, если Вк = {t>i,• ■ ■ ,u2»}, то

или при фиксированном упорядочении вершин Вк можно принять такое описание окрестности Уь{а):

где 5, > 0 и

2*

=п-к+1

>=1

Аналогично определим окрестность порядка < к слове о 6 В" как следующее множество

к

= У к (а)

Г=1

Определение 2. Слова а,Ь € Вп называются к(< к)— эквивалентными, если И(а) = 14(6) или У<к(а) = У<к(Ь)

Эти отношения к(< к)— эквивалентности являются обычными отношениями эквивалентности в чисто алгебраическом смысле и нотому весь куб В" может быть представлен в следующем виде

а

где W^¡(a)— это класс к— эквивалентности, определяемый словом а е В". Аналогично

а

В содержательном смысле класс И^(а)— означает, что все его элементы "неотличимы" по окрестности порядка к от слова а 6 В". Таким образом "точность" задания слова а с помощью окрестности порядка < к измеряется мощностью класса эквивалентности И'<*(а).

Далее в главе II предлагается алгоритм для построения классов эквивалентности Игк(а) и ХУ^а). Этот алгоритм формулируется в терминах логического перманента булевой

матрицы и использует некоторые идеи из аналогичных построений для случая распознавания по фрагментам [2].

Алгоритм построения классов эквивалентности.

Пусть х — (Х]Х? ■ ■ ■ х„) 6 ВРассмотрим все подслова длины к слова V = (1,2,3, • ■ ,п)-VI = (1,2,3, ••• ,к), у2 = (2,3,4,-■ • ,¿ + 1),- ■ ■, «п-*+1 = {п-к + 1,п-к + 2, ■ ■ ■ ,п). Пусть теперь < х,ь > - бинарная операция "проектирования" слова х на "подслово" V, т.е.

< X, VI > = ХуХ2 ■ ■ -Хк

< х, 1)2 > = хгхг ■ • ■ Хк+1

< х, > = хп-к+1Хп-к+2 •■•Хп

Таким образом с помощью операции < х, V > из слова х "вырезается" его подслово, соответствующее V или с координатами из множества V. Пусть теперь А < V, е > — множество всех решений уравнения

<х,у>=е (2)

Здесь V = (¿112■••г*), е = (е^-'-вк) € Вк, х = (а^г • • • ж„) е В". Таким образом А(у, е)— это множество двоичных слов длины п "проектирование" которых на оси {чь •■•'*) приводит к слову е. В терминах булевой алгебры это множество выглядит следующим образом.

Лемма 1. Справедливо соотношение

Другими словами А(у, е)— это (п — к)— мерный подкуб В" или элементарная конъюнкция ранга к.

По схеме (1) сформируем логическую матрицу А — ||АЧ||. Эта матрица имеет размеры (п — к + 1) х (п - к + 1). Под логическим перманентом матриц А мы будем понимать

следующую Д.Н.Ф

per А = У АитА2а(2) ■■■А п— k+ltr(n—к+1) <r6S(n-fc+1)

Здесь Sn-*+1- симметрическая группа порядка (п — к + 1). Теорема 1. Класс эквивалентности Wjt(a) описывается следующий формулой

Wk(a) = per А

Таким образом множество элементов класса эквивалентности Wjt(a) совпадает с множеством единиц булевой функции Д.Н.Ф. которой есть per А.

Далее в этой главе строится описание классов эквивалентности W<k{a)- Эти классы также описываются с помощью перманента логической матрицы которая явля-

ется "клеточной" матрицей с блоками А*, ■ • ■,

В главе II строится "алгебраическое" описание классов эквивалентности Wa(n) для "малых" к = 1,2 и приводится общая схема такого описания.

Пусть х — (xix2 • ■ ■ хп) € Вп, а = (aja^ ■ • • a*) € В* и ta(x)— число вхождений слова а в слово ж в качестве подслова. Другими словами -ta(x)- это кратность вхождения слова а в мультимножество Vi(i), определенное выше. Если

Д.О _ I х* при а = 1 I 1 - х, при а = О то справедливо следующее утверждение.

Лемма 2.

ш = £ «л (з)

1<«<»-*+1

Таким образом ta(x)— это полином от п— переменных степени к. С помощью леммы 2 доказываются следующие утверждения.

Теорема 2. Слова х и у из Б" являются 2- эквивалентными тогда и только тогда, когда выполняются условия

1) S(x)=S(y)

2) ||®|| - IMI =x1-yi=xn-yn

Теорема 2 позволяет провести проверку 2-эквивалентности слов из В" за линейное по входу время, т.к. вычисление S(x) и ||х|| может быть сделано с линейной сложностью от п.

Отметим также, что в работе [4] предложен алгоритм установления 2-эквивалентности слов длины п над произвольным конечным алфавитам, имеющий сложность 0(п4)

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

Теорема 3. Слово а € В" однозначно определяется своими подсловами длины S если и только если выполняются следующие условия: 1) S(a) < 2

S) а = 77п~27 и п > 4

3) а = 7777• • • 77 и п = 0 (mod 2) (п > 2).

Отметим также, что в работе [4] предложено "алгоритмическое" решение задачи о восстановим ости, если это возможно, слова длины п по подсловам длины два в случае произвольного конечного алфавита. Сложность такого алгоритма 0(п4).

Описание классов (< 2)— эквивалентности содержатся в теореме 3.

Теорема 4. Слова х и у из В" являются < 2 -эквивалентными если и только если выполняются следующие условия

1) S(x) = S (у) 3) xi = уи хп = уп

2) M = |М|

Так как имеет цепочка включений

• • • Ç W<k(a) С W<*_i(a) С W<k-2(a) С ■ ■ ■

то начиная с некоторого к эта цепочка стабилизируется, что означает следующий факт' Слово а однозначно определяется своими подсловами длины < к. Значение этого к как функции от а € Л™ мы обозначим через А„(а)

Пусть

An = max А„(а) лев*

Теорема 5. Справедливо равенство

Это теорема показывает, что задача о восстановлении слова длины п по "различным" фрагментам и задача восстановлении слова по всем подсловам (с учётом кратности) приводят к одной и той же величине длины "частей", необходимых для однозначной реконструкции.

Глава III.

В главе III рассматривается задаче "различимости" слова по подсловам без учёта их кратности.

Пусть х, у 6 В" и Т(х,у)— множество всех слов, являющихся подсловами х, и не являющих подсловами у. Любое слово а € Т(х, у) называется "различающим" х и у. Любое слово из множества Т°(а;, у) = Т{х,у) U Т(у, х) называется тестовым для пары (х,у) е В" х Вп. Задача состоит в нахождении или построении слова минимальной длины из множества Т°(х,у). Любое такое слово называется минимальным тестом, а длина его обозначается через t(x,y). В содержательном смысле чем больше величина t(x, у) тем ^труднее" различать слова хну или, по другому, тем более они "похожи".

Замечание. Если х — у, то t(x, 2/)=f|x|-Рассмотрим следующую функцию, характеризующую меру различия слов х, у € В":

d(x, y) = n-t(x,y)

Лемма 3. Функция d(x,y) является псевдометрикой на В". Метрикой этой функции "мешает" быть то обстоятельство, что

d((10)"'/2, (01)"-'2) = О

в то время как (10)"/2 ф (01)"/2.

Функция t(x, у) имеет довольно сложную комбинаторную природу и потому поиски хороших аппроксимаций для неё весьма актуальны.

Определение 3. Пусть х 6 В" Величина 8(х) называется типом слова х, если в х в качестве подслова фигурируют все слове длины < 5(х) и нет хотя бы одного подслова длины б(х) +1.

Лемма 4. Справедливы неравенства

1) t(x1»)>min{i(x),J(y)} + l

(6)

2) S(x) ф S(y), t(x, у) < min{i(x), ¿(у)} Для S(x) в свою очередь справедливы следующие границы

2S(I) + 6(х) < п + 1

и таким образом

+ (7)

п + 1

Следующая "аппроксимация" использует серийное представление слов. Пусть х = "jmi!ym* ■ ■ ■ 7mr, у - 7П17П2 • • • 7П%

S*(x) = {m2,mз, • • • ,mr_i}, Sl(y) — {га2,Пз, • • ■ ,n,_i} и S1(x)AS1(y)- симметрическая разность множеств Sr(x) и S1(y)

Лемма 5. Если р € Sl(x) Д Sl(y), то выполняется неравенство

t{x,y)<p + 2 (8)

Границы (7) и (8) наводят на мысль, что в "типичном" случае функция t(x, у) растёт не быстрее log2 п. Определённым подтверждением этой гипотезы является следующие утверждение.

Теорема 6. Для "почти всех" пар точек (х,у) € В" х В" длина минимального теста не превосходит асимптотически log2 п.

В этой же главе предложен алгоритм для построения минимального теста t(x,y) для произвольных слов (х, у)еВпх В".

1. V.K. Leont'ev, M.R. Hooshmandasl, Channel with separation of errors\\ Тез. докл. конф. "Дискретный математика и ее приложения". Москва, Мехмат, МГУ,2004. С.

2. В.К. Леонтьев, М.Р. Хошманд Асл, О множествах двоичных слов, содержащих фиксированное подслово\\ Тез. докл. конф. "Дискретный анализ и исследование операций". Новосибирск, 2004. С.89.

3. V.K. Leont'ev, M.R. Hooshmandasl, Characterization words by subwords \\ Тез. докл. конф. Annual iranian mathematics conference",Iran, Yazd, 2005. C.120.

Публикации по теме диссертации

427-428.

Напечатано о готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано к печати 21.11.2005 г. Формэт 60x90 1/16. Усл.печл. 0,75. Тираж 100 экз. Заказ 805. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

i

i i

06-970

¡>

1 Введение

1.1 Реконструкция по подсловам.

1.2 Различимость слов.

2 Реконструкция по подсловам

2.1 Подслова, окрестности, классы эквивалентности.

2.2 Описания классов эквивалентности в терминах логического перманента.

2.2.1 Классы эквивалентности Wk{x)

2.2.2 Классы эквивалентности W<k(x).

2.3 Серийное описание классов эквивалентности.

2.3.1 Характеризация < 2 -эквивалентности.

2.4 Восстановление слова по подсловам длины > [|] +

3 Различимость слов

3.1 Различающие слова, тестовые множество, тесты.

3.2 Свойства и оценки функции t(х, у).

3.3 Алгоритм построения минимального теста.

3.3.1 Простейший алгоритм.

3.3.2 Префикс-функция, ассоциированная с образцом

3.3.3 Алгоритм Кнута - Морриса - Пратта.

3.3.4 Алгоритмы нахождения t(х, у).

1.1 Реконструкция по подсловам Часть и целое всегда является предметом изучения науки. Основной философский вопрос при таком изучении звучит так: как устроен мир? Еслипри исследовании информацию принят следующий тезис:Всякая информация может быть представлена словом в конечном алфавите, то часть проблем, связанных с понятием информация может бытьсформулировано в виде изучения слова и его частей. Что понимать под частью слова зависит от контекста изучаемой проблемы и точные постановкизадач могут варьироваться в достаточно широких пределах? В целом такого роде задачи имеют глубокие связи с алгеброй, топологией, теориейчисел,теорией информации и математической генетикой.Основным объектом изучения в диссертации являются слова конечнойдлины над бинарным алфавитом {0,1}. Это множество обозначается черезв*. Если X = xiX2 • • • Хп- слово из Б*, то любое слово виданазывается подсловом х. При этом 1 <к <п—г. Таким образом множествовсех подслов длины к слова х содержит не более чем (п — А; + 1)— различных подслов и обш,ее число подслов слова длины, с учётом их кратности,равно ("^^) • Каждое подслово а слова х несёт определённую информациюоб этом слове. Как оценить или измерить эту информацию? Этот вопросявляется одним из ключевых вопросов, рассматриваемых в этой диссертации. Интуитивно ясно, что чем длиннее подслова слова ж, тем большенесут они информации об исходном слове. В каком случае слово можнооднозначно восстановить по набору его подслов ограниченной длины и вкаком случае это можно сделать лишь с определенной погрешностью? Всеэти вопросы уже рассматривались в целом ряде исследований, относяш,ихся к комбинаторике слов и на многие из них получены ответы той илииной степени полноты и определённости. Однако вопросы восстановимостии различимости формулировались в основном по отношению к фрагментам слова, а не к под словам. Фрагмент- это более широкое понятие частислова, чем только подслова ограниченной длины. Однако подслово- это боли структурированная часть слова, чем фрагмент, что также привноситопределённую специфику в проблему восстановимости и различимости поподсловам. Пусть В — {0,1}— двоичный алфавит и В*— множество всехслов конечной длины над алфавитом В. Если х = (a;iX2 • • • Хп) Е В*, тодлину слова х мы будем обозначать через \х\. Множество всех бинарныхслов длины п и < п мы будем обозначать соответственно через В"^ и В-"^.Множество В* является моноидом с операцией конкатенациих,у G В* -)-ху е В*Определение 1.1.1. Слово у = {у\У2'"Ук) называется подсловом словаX = (xiX2 • • -Хп), еслиХГ = УЪ ^i+i = У2Г'- , Xi+k-i = Укдля некоторого г из интервала [1,п — к + 1].Слово у = {у\У2'"Ук) называется фрагментом слова х =если существует такая последовательность 1 < ii < 12 < - • • < ik < п,чтоXii =yi,Xi^=y2,--- , Xik = УкЗамечание. У части авторов исследований по комбинаторике слов используется несколько отличная терминология. Так в монографии[1] подслово (subword) в нашей терминологии- это фактор (factor), а фрагментэто подслово. Мы будем придерживаться введённых выше обозначений,понимая всю условность преимуш,еств и недостатоков различных терминологий.На множестве В* введём частичный порядок (<) , положивX <уесли X— является подсловом слова у.Пусть а Е 5* и 14(а)— мультимножество всех подслов длины к у слова а.Пример. Если бп = (01)" = 1010 • • • 10 G Л", точто означает что нодслово "1" входит в £„ ^ рэ-з и подслово "О"- входитв £п — ^ — раз.Аналогичнов тех же терминах. При этом |Vi(£:n)| = 2п, |F2(£^n)| = 2п — 1.АналогичноВ содержательном смысле класс Wk{a)— означает, что все его элементы"неотличимы" по окрестности порядка к от слова а £ Б " . Таким образом"точность" задания слова а с помош,ью окрестности порядка < к измеряется мош,ностью класса эквивалентности И^<^(а).Далее в главе / / предлагается алгоритм для построения классов эквивалентности Wk{a) и W<f.{a). Этот алгоритм формулируется в терминах логического перманента булевой матрицы и использует некоторые идеи изаналогичных построений для случая раснознавая по фрагментам [2].Алгоритм построения классов эквивалентности.Пусть теперь А < v,e > — множество всех решений уравнения<x,v>=e (1.2)Здесь V = {iii2 • • • ik), е = (eie2 • • • вк) G В^, х — (жхжг • • • Хп) G -В". Такимобразом A{v^ е)— это множество двоичных слов длины п "проектирование"которых на оси {iii2 • • • u ) приводит к слову е. В терминах булевой алгебрыэто множество выглядит следующим образом.Лемма 1.1.1. Справедливо соотношениеДругими словами A{v^e)— это {п — к)— мерный нодкб, В'^ или элементарная конъюнкция ранга к.По схеме (1.1) сформируем логическую матрицу А = \\Aij\\. Эта матрицаимеет размеры {п — к -\- 1) х [п — к -\- 1). Под логическим перманентомматрицы А мы будем понимать следующую Д.Н.Ф= \JЗдесь Sn-k+i— симметрическая группа порядка {п — к + 1).Теорема 1.1.1. Класс эквивалентности Wk{a) описывается следующийформулойWk{a) = per АТаким образом множество элементов класса эквивалентности Wk{a) совпадает с множеством единиц булевой функции Д.Н.Ф. которой есть per А. Далее в этой главе строится описание класса эквивалентности H^<fc(a).Этот класс также описывается с помощью перманента логической матрицыА^1с{а), которая является "клеточной" матрицей с блоками А^,в главе (2) строится "алгебраическое" описание классов эквивалентностиWk[a) для "малых" А; = 1, 2,3 и приводится общая схема такого описания.Пусть X — {х\Х2 • • -Хп) £ -В", а = {aia2 • • • а^) Е В^ и ta{x)— число вхождений слова а в слово х в качестве подслова. Другими словами -ta{x)это кратность вхождения слова а в мультимножество Vk{x), определенноевыше.Если г Xi при а = 11 — Xi при а = Ото справедливо следующее утверждение.Лемма 1.1.2.10Таким образом ta{x)— это полином от п— переменных степени к.Теорема 1.1.2. Слова х и у из В"^ являются 2— эквивалентными тогда^ и только тогда, когда выполняются условияS{x) = S{y)(1.4)2) Ы - \\y\\ =Х1-у1 = Хп-УпТеорема 1.1.2 нозволяет провести проверку 2-эквивалентности слов изВ^ за линейное по входу время, т.к. вычисление S{x) и \\x\\ может бытьсделано с линейной сложностью от п.Отметим также, что в работе [4] предложен алгоритм установления 2эквивалентности слов длины п над произвольным конечным алфавитам,имеющий сложностьИз Теоремы 1.1.2 можно получить условия, при которых любое слово изБ " однозначно определяется своими подсловами длины 2.11Теорема 1.1.3. Слово а G В" однозначно определяется своими подсловами длины 2 если и только если выполняются следующие условия:1) S{a) < 22) а = 77 "^7 и п>43) а = 7777 • • • 77 •" ^ = О (mod 2) (п > 2).Отметим также, что в работе [4] предложено "алгоритмическое" решениезадачи о восстановимости, если это возможно, слова длины п по подсловамдлины два в случае произвольного конечного алфавита. Сложность такогоалгоритмаОписание классов (< 2)— эквивалентности содержатся в теореме 1.1.4.Теорема 1.1.4. Слова х и у из В^ являются < 2 -эквивалентными еслии только если выполняются следующие условия1) S{x) = S{y) 3) xi = Ух, Хп = Уп(1.5)2) \\x\\ = \\y\\Так как имеет цепочка включений• • • С W<k{a) С И^<А.-1(а) С W<k-2[a) С • • •то начиная с некоторого к эта цепочка стабилизируется, что означает следующий факт:Слово а однозначно определяется своими нодсловами длины < к. Значение12этого к как функции от а £ В" мы обозначим черезПримеры.1. Если а = О", то Хп{а) = 12. Если а = ОЧ"-^ то Хп(а) = 2, т.к.иV2(a) = {0^ Г - ^По V2{a) слово а восстанавливается однозначно, т. к. структура У2{а) показывает, что у слова а равно 2 серии (если бы не так, то в V2(a) входилибы слова (01) и (10).) и слово начинается с нуля.ПустьТеорема 1.1.5. Справедливо равенствоЭто теорема показывает, что задача о восстановлении слова длины ппо "различным" фрагментам и задача восстановлении слова по всем подсловам (с учётом кратности) приводят к одной и той же величине длины"частей", необходимых для однозначной реконструкции.

1. Lothaire М.// Combinatorics on Words. Encyclopedia of Mathematics and its Application Reading. M1.: Addition-Wisely.Publ. Co, 1983.

2. Леонтьев В.К.// Задачи восстановления слов по фрагментам и их приложения. "Дискретный анализ и исследование операций", 1995, Т. 2, № 2. С. 26-48.

3. Зенкин А. И., Леонтьев В.К.// Об одной неклассической задаче распознавания, Журнал вычислительной математики и математической физики. 1984, Т. 24, № 6, С. 925-931.

4. Сметанич Я. С.// О восстановлении слов, Труды Математической института, А. Стеклова. М. "Наука", 1973, Т. 83, С. 183-202.

5. Леонтьев В.К., Сметанин Ю. Г.// О восстановлении векторов набору их фрагментов//Докл. АН СССР. 1988, Т. 302, № 6.

6. Журавлев Ю. И.// Об алгебраическом подходе к решению задач распознавания и классификации // Проблемы кибернетики.М.:Наука,1978.

7. Леонтьев В. К.// Распознавание двоичных слов по их фрагментам // Докл. РАН. 1993. Т. 330, № 4. С. 434-436.

8. Калашник В. В.// Восстановление слова по его фрагментам // Вы-числ. математика и вычисл. техника. Харьков, 1973. Вып. 4. С. 56-57.

9. Simon I.// Piecewise testable events // Automata Theory and Formal Languages. Berlin etc.: Springer-Verl., 1975. P. 214-222. (Lecture Notes in Com-put. Sci.; V. 33).

10. Burosch G., Frankl U., Rohl S.// Uber Ordnungen von Binaworten // Rostock Math. Kolloq. 1990. N 39. P. 53-64.

11. Алиев Ш. M.// Алгоритмические вопросы построения оптимальных кодов для многих приемников: Дис. . канд. физ.-мат. наук. М., 1993.

12. Сметанич Я. С. // О восстановлении слов // Докл. АН СССР. 1971. Т. 201, № 4. С. 798-800.

13. L.J.Guibas and A.M.Odlyzko //Periods in strings. J. Comb. Theory (A) 30 (1981), 19-42.

14. L.J.Guibas and A.M.Odlyzko // String overlaps, pattern matching, and non-transitive games. J.Comb. Theory (A) 30 (1981), 183-208.

15. A.M.Odlyzko// Enumeration of Strings AT'T Bell Laboratories, Murra Hill, New Jersey 07974 USA.

16. Т. Кормен, Ч. Лейзерсон, P. Ривест// Алгоритмы: построение и анализ/ Пер. с англ. под ред. А. Шеня/ МЦНМО: БИНОМ. Лаборатория знаний, 2004.

17. Lothaire М.// Applied Combinatorics on words//Version June 23, 2004.