автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Реконструкция по частичным представлениям в комбинаторике слов

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

СМЕТАНИН ЮРИЙ ГЕННАДИЕВИЧ

РЕКОНСТРУКЦИЯ ПО ЧАСТИЧНЫМ ПРЕДСТАВЛЕНИЯМ В КОМБИНАТОРИКЕ СЛОВ

Специальность - 05.13.17 Теоретические основы информатики

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

Москва-2004

Работа выполнена в Научном совете РАН по комплексной проблеме «Кибернетика»

Официальные оппоненты: д.ф.-м.н., профессор В.А. Зиновьев д.ф.-м.н., профессор A.A. Сапоженко д.ф.-м.н., профессор Л.Н.Столяров

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

Институт системного программирования РАН

Защита состоится " <0 "ЩгрМЯ. 2004 г. в 10 часов на заседании диссертационного совета Д002.017.02 при Вычислительном центре им. А. А. Дородницына РАН по адресу 119991, Москва, ГСП-1, ул. Вавилова, 40, конференц-зал.

С диссертацией можно ознакомиться в библиотеке

ВЦ РАН

Автореферат разослан "3 "МССрМсдШ

г.

Ученый секретарь диссертационного совета

Д002.017.02 при ВЦ РАН

д.ф.-м.н.

/ Рязанов В.В./

ао<пЦ

ШЛ

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

Актуальность темы. Диссертация посвящена задачам восстановления полной информации по ее частичным описаниям. Эти задачи возникают в распознавании образов, теории кодирования, комбинаторном синтезе | последовательностей протеинов, теории ДНК-

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

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

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

Спецификой теории реконструкции как раздела комбинаторики слов является ее основная задача: синтез слов по частичным представлениям. Эта теория, возникшая в результате интеграции алгебраической комбинаторики слов с методами теории кодирования и алгебраического распознавания образов, закладывает методологическую основу реконструкции

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

Цель работы - построение математической теории реконструкции слов по их частичным описаниям в случае, когда задана совокупность правил, в соответствии с которыми образуются искаженные версии слова, а набором частичных описаний является совокупность фрагментов, каждый из которых образован в соответствии с правилом из этой совокупности и разработка на основе этой теории методов решения следующих задач:

- определение классов слов, обладающих одинаковыми частичными описаниями при заданных правилах образования фрагментарных представлений;

- алгебраическое описание классов эквивалентных слов;

- разработка эффективных алгоритмов точной и приближенной реконструкции слов;

- построение обучающихся систем реконструкции.

Научная новизна. Построена теория реконструкции

по частичным представлениям, позволяющая описать связь задач реконструкции с другими направлениями научных исследований в комбинаторике слов. Выделены основные модели реконструкции в рамках этой теории. Проведен анализ алгоритмической сложности задач реконструкции. Классы слов, эквивалентных с точки зрения реконструкции по заданному множеству фрагментов, описаны в терминах решений диофаНтовых уравнений определенного вида. Представлены границы длин фрагментов, при которых обеспечена однозначность реконструкции, в случае полного мультимножества и полного множества фрагментов. Во втором случае эти границы являются жесткими и построен алгоритм реконструкции за линейное время. Для случаев, когда известны определенные дополнительные ограничения на правила образования фрагментарных представлений, предложены детерминированные и стохастические алгоритмы реконструкции. Описаны их применения в распознавании образов и анализе изображений. Исследованы нейросетевые модели в неархимедовых числовых полях, полезные в задачах реконструкции слов. Предложены алгоритмы устранения некорректных решений в нейронных сетях и повышения емкости нейронных сетей; первый основан на методе случайных выборок, второй - на разреженном кодировании.

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

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

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

Апробация работы. Результаты диссертации

докладывались на следующих конференциях - и

семинарах:

-Всесоюзной конференции "Математические методы распознавания образов", Дилижан, 16-21 мая 1985;

- Всесоюзной конференции "Методы и средства обработки графической информации", Горький, 1985 г.;

- Второй Всесоюзной конференции "Автоматизированные системы обработки изображений", Львов, 1986 г;

-First Int. Conf. on Information Technologies for Image Analysis and Pattern Recognition ITIAPR'90, Львов, 1990 г.;

- Международной конференции "Проблемы космического и спутникового мониторинга территорий Казахстана", Алма-Ата, 1993;

- Второй Всероссийской с участием стран СНГ конференции "Распознавание образов и анализ изображений: Новые информационные технологии", Ульяновский государственный технический университет, Ульяновск, 1995 г.;

- Fifth Open German-Russian Workshop on Pattem Recognition and Image Understanding:, 1998 г., Херршинг, Германия;

-Четвертой Всероссийской с международным участием конференции «Распознавание образов и анализ изображений: новые информационные технологии», Новосибирск, 1998 г.;

-Шестой Всероссийской с участием стран СНГ конференции «Методы и средства обработки сложной графической информации», Нижний Новгород, 2001 г.;

-Twelfth Scandinavian Conference on Image Analysis, Stavanger, Norway, 2001 r.

Результаты работы были использованы в проектах РФФИ, ГНТП «Прогрессивные информационные технологии» и «Информатизация России», международной программы INTAS.

Публикации. По теме диссертации опубликовано 20 работ (6 работ - в соавторстве).

Структура диссертации.

Диссертация состоит из введения, пяти глав и библиографии. Объем диссертации - 201 страница, список литературы содержит 268 наименований. В работу включены 8 рисунков.

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

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

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

Формальная постановка задачи реконструкции

Пусть задано множество Е" слов длины .п. Предполагается, что зафиксировано некоторое множество V подпоследовательностей

последовательности {1, 2, ... ,п). Для каждого слова а е Е" рассматриваются только такие его фрагменты (подпоследовательности), которые порождаются множеством подпоследовательностей V = {у1 у2 ... Vм}. Каждую подпоследовательность из V можно считать каналом с искажениями. Подпоследовательность / е V задана характеристическим набором (/[ /г • • • уг„) таким, что у,- = 1, если г-й символ слова входит во фрагмент, полученный с помощью /, и у,- = 0 в противном случае.

Процедура получения из слова а фрагмента с помощью характеристического вектора у =

{(/' I ~ ' *2' ' ^ описывается в виде операции

фрагментирования <а, у> = (я. а^ ... а^). При получении

фрагмента Ь е Е^ неизвестно, от действия какого именно характеристического вектора на исходное слово получен этот фрагмент.

В данной формулировке задачи вся информация о слове х е ЕР, полученная на выходе ■ канала V, заключается в мультимножестве или множестве У(х). Требуется определить, насколько полно эта информация определяет исходное счово х еЕ". В дальнейшем модель с мультимножеством У(х) называется первой моделью реконструкции. Случай, когда кратности фрагментов неизвестны, а известно только, входит ли каждый конкретный фрагмент в множество У(х), называется второй моделью реконструкции.

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

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

В § 2 приведена формальная постановка задачи реконструкции слов по фрагментам. Определены две модели реконструкции слов - с учетом кратности вхождения фрагментов в слово (первая модель) и без учета кратности вхождения фрагментов в слово (вторая модель).

В § 3 изучена алгоритмическая сложность задач о существовании и единственности реконструируемого слова.

Алгоритмическая сложность задачи о существовании неизвестного слова а с заданным набором фрагментов {<а, у>}, V е V, описана следующим утверждением.

Задача К\. Пусть даны целое число п, характеристическое множество V = {уь ... , у,„}, у,- е Еп,

I V,-1 = 3, / = 1,2,..., т, и набор векторов Ьр] =1,2,..., т; требуется определить, являются ли векторы 6у фрагментами некоторого вектора длины п, то есть существует ли вектор Ь е Е„ такой, что для некоторой

перестановки ( 1 выполняются равенства

\J\Jl •••Ли /

<Ь, У;> = Ър, / = 1,..., т.

Теорема 1. Задача ЛI является ИР-полной.

Доказательство основано на сведении задачи «3-выполнимость» к задаче А

Доказано также следующее непосредственное следствие предыдущего утверждения. Если набор векторов = 1, 2,..., т, является набором фрагментов некоторого вектора длины Ъ е Е„, то проверка наличия другого вектора, для которого они также являются набором фрагментов, тоже является ЫР-полной.

Задача Ац. Даны: целое число п, характеристическое множество У = {уь •» , Ут}, у,- е Е,,2, /=1,2,..., т, и набор векторов В. = Щ} с Ег, } = 1, 2, ... , г. Требуется определить, существует ли вектор л: длины п такой, что множество {<5с, У>} = Я.

Теорема 2. Задачами является ИР-полной.

Доказательство основано на сведении задачи «Вершинное покрытие» к задаче Ли.

Пусть даны характеристическое множество V = {у1, ..., о/"}, у' е Еп, | у' I = / = 1,2,..., т, и набор слов В = {¿>ь ... , Ьт), который получен из некоторого слова а1 с помощью фрагментарного множества V. Требуется найти

это слово а1, то есть найти перестановку I ^ "'), для

которой выполняются равенства

<а', у,-> = Ьт, / = 1,..., т.

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

где / = 1, ... ,р, /,у = 1, ..., т, а1 е А, У е В, V1 е V, а р -некоторая мера соответствия слов из р(х, х) = 0, | р(х, >0прихфу.

В случае, если р является векторной мерой, задача становится многокритериальной. Решение задачи в данном случае сводится к нахождению назначений заданного веса в матрицах, построенных для каждой компоненты векторной меры. Эта задача является НР-полной, но не в сильном смысле. Для ее решения разработан псевдополиномиальный рандомизированный алгоритм. Его полное описание представлено в общем виде (§ 6).

В § 4 изучена зависимость сложности задач реконструкции слов от алфавита.

Утверждение. Если множество V является полным на двоичном кубе Еп , то оно является полным и на любом г-значном кубе Еп(г), г = 3, 4, ... . Доказательство этого утверждения основано на анализе проекций Е„(г) на Еп(г): {/ 10 при/ г = 0,1,..., г- 1}.

Именно этим утверждением оправдан тот факт, что в работе изучаются в основном двоичные векторы.

Аналогичное утверждение верно и для неполных классов. Это оказывается полезным в изучении мощности классов эквивалентности в произвольном конечном алфавите.

Переход к двоичному случаю позволяет получить дескриптивное описание класса У'(а) в терминах ДНФ, определяемых теоретико-множественными

перманентами.

В § 5 изучены сжимающие классы V, расширение которых приводит к сужению классов эквивалентности и, тем самым, к увеличению информации о реконструируемом слове.

Доказано, что Г-множества Е„к (сфера) и Е„к и Епк'х и ... и Еп (ограничиваемый ею шар) являются

конгруэнтными, то есть порождают разбиения на одни и те же классы эквивалентности. Доказательство основано на приведенном в предыдущем параграфе сведении к теоретико-множественным перманентам.

В диссертации рассмотрено несколько задач реконструкции и распознавания слов, связанных с оптимизацией выбора фрагментирующих множеств, в том числе и по многим критериям. Эти задачи сводятся к поиску оптимальных траекторий в матрицах и графах. Для решения "таких задач предложен класс псевдополиномиальных алгоритмов стохастической оптимизации. § 6 посвящен описанию этих алгоритмов. Подробно описан алгоритм поиска диагонали заданного веса в целочисленной матрице; все последующие алгоритмы являются его прямыми обобщениями.

Пусть А - матрица размера п х п с целыми

элементами а», к — шах а„ , 5 = {я} - множество ее

'V 1

диагоналей, Ы = п\, Л (я) = лад + аад + ••• + Ялф) - вес назначения Требуется определить, имеется ли в матрице А назначение требуемого веса а,

А($) = а, 5 е Я.

NР-полнота этой задачи доказана сведением задачи о ранце. Предлагаемый алгоритм решает поставленную задачу о назначениях за время, полиномиальное по п и к Алгоритм является рандомизированным и позволяет работать с несколькими независимыми критериями. Он никогда не ошибается и доказывает существование приемлемого решения либо отказывается от ответа (то есть относится к классу алгоритмов Монте-Карло). Вероятность отказа в случае существования решения - не более (1 - 1/(2/*)) для одного теста; здесь к - максимум

абсолютного значения элементов. Число вычислительных операций - 0(n3h(n + log h)), объем памяти должен быть достаточен для хранения п2 чисел длины log{nh). Повторные тестирования с независимыми случайно выбранными параметрами дают возможность сделать вероятность получения правильного ответа сколь угодно близкой к единице.

Пусть Р - простое число, Р е (2nh + 2, 4nh + 4). Все вычисления проводятся в поле GF(P)

Для любых осц, ... , а„„ , выбранных независимо с равными вероятностями из GF(P),

Е-*""det ацх*II =

*=l seS jt=l

где o(s) - четность перестановки, соответствующей назначению s. Поскольку - а\ < 2nh < Р - 1, все внутренние суммы с A(s) -аФ 0 обращаются в нуль, F(an,...,aJ= X (-О^Чо,.,^) •

seS,A(s)=a

Следовательно, многочлен F является многочленом степени п от п2 переменных a¡j, содержащий столько мономов aij(i) ... а„5(„) с коэффициентами ±1, сколько диагоналей веса а имеется в матрице А.

Если таких диагоналей нет, F = 0(mod /*) при любых cxu(i)... а,ф), если они есть, то F может обратиться в нуль из-за неудачного выбора параметров <хь(1)... a„s(„). Число решений N(P) этого сравнения для многочлена F(x\,...,Хк), не все коэффициенты которого делятся наР, удовлетворяет неравенству

N(P) < Рк~] deg F, где deg F - полная степень многочлена F.

При к = п2, deg F = п получается оценка

Процедура повторяется в итеративном режиме: если при выбранных осц, ..., а„„

.....)а,л) ^ 0(тос1Р),

то задача имеет решения; если при выбранных ... ,апп

F(alp...,aJsO(mod^>),

выбираются новые ац,..., а„„, и процесс повторяется.

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

В главе II изучена I модель реконструкции. Предполагается, что зафиксировано некоторое множество V подпоследовательностей

последовательности 1,2,..., п. Для каждого слова а е Е" рассматриваются только такие его фрагменты (подпоследовательности), которые порождаются множеством подпоследовательностей V. Каждая подпоследовательность V е V задана характеристическим набором (VI Уг ... V,,) таким, что V/ = 1, если г е V, и V,- = 0 в противном случае. На выходе получается именно мультимножество, а не мультипоследовательность, то есть при получении фрагмента Ъ е ¥1(а) мы не знаем, от действия какого именно характеристического вектора на исходное слово получен этот фрагмент.

В § 1 описано сведение задачи реконструкции к решению определенной системы диофантовых уравнений. Эта система зависит от конкретного вида V-множества.

Построение системы уравнений основано на использовании следующего равенства для числа вхождений слова а = (щаг ... ат) е ъх = (х\ хг ... хп) е£"в качестве фрагмента при множества V*:

<Х\<*г-атУу.

= Е (ЬЛ + Ч XV,2 + «2 )...(Ьтх,я+ат)'

где ак = 1 - а*, Ък = 2ак-\.

Доказана следующая теорема о сведении Г-эквивалентности к решению диофантовых уравнений.

Теорема. Слова а = (а\ ... а„) и Ь = ... Д,) являются ^-эквивалентными тогда и только тогда, когда выполняются соотношения

У Л/?г":Аа,а, ...а, =

I 1|'2—'I '2 '»

1 < 5 < 1 < I < т, Л определяются кратностями вхождения фрагментов при заданном Г-множестве. Для случая У~Е„к параметры X имеют вид

и-ии-^.-и-и-л

1 <1'ь ..., Ь^п.

В § 2 изучены условия полноты Г-множества Е„к. В этом случае проверка эквивалентности слов сводится к вычислению моментов.

Теорема. Слова* с единичными координатами (хь ... , хт) и у с единичными координатами (уь ... , ут) являются Г-эквивалентными тогда и только тогда, когда равенства

т т тп

'1=1 '2>'|

т т т

'1=1 '2>'|

вьшолняются при всех с? > 0, р^ %>0 таких, что

с/

у=1

Теорема. Характеристическое множество V* является полным тогда и только тогда, когда система уравнений

1<$< #¡,1 < г < т < п имеет не более одного решения в числах (0, 1) при любой правой части.

Из этой системы выведены уточненные оценки необходимой и достаточной длины фрагментов, при которой множество У= Е„к является полным.

В § 3 получено уточнение верхней границы к < спт. Для ее получения использовалась чебышевская аппроксимация приведенной выше системы уравнений для моментов. С ее помощью строится многочлен степени не более /л < 2,11 л/п +4 с вещественными коэффициентами такой, что

/Ф) >|/(1)| + |/(2)| + ...|/(л)|. Отсюда следует, что

значение ДО), определяющее первую компоненту реконструируемого слова, однозначно определяется по

правой части системы уравнений для моментов. Многочлен имеет вид

f{x) = {g(\-2xln))\ где = |Т0(.х) + Т1(х) + Т2(х) + ...+Т,(х),

Т, (л) = cos(/ arccos х) - многочлен Чебышева первого рода.

В § 4 доказана следующая оценка нижней границы к. Теорема. Пусть п(к) - длина наименьших V-

эквивалентных слов при V = is*. Тогда при к > 3 выполняется рекуррентное соотношение п(к+ 1 )>п(к) + п(к- 1)+ 1. Утверждение доказывается прямым построением V-

эквивалентных слов для V = Е^, удовлетворяющих

этому соотношению.

Для к = 1 существует пара неразличимых слов длины п = 2:

ах={ 01),= (10), имеющих одинаковые мультимножества фрагментов по окнам {(01), (10)}:

V(al) = {0,1} = V(J5X). Для к = 2 пара неразличимых слов длины п - 4 получается склейкой а1 и /?':

а2 = cit ft - (0110), - (0110).

Легко видеть, что V = образует для о? и ft одинаковые мультимножества фрагментов, V(a?) = {00, 01,01, 10, 10, 11} = V(ft).

Продолжая таким же образом, получим последовательность пар векторов длины 2к,

неразличимых по множеству окон Vk = Е/-У Действительно, пусть et и 0е неразличимы по Произвольный вектор у б Ek+\ можно представить в виде

У=9/, 9 еЕш-ф ? eEq.

При q>0viq<k+l

t^ctf?) = tYX(ct) t^) tJJ?c?) = trX(ß)t^c?). Поскольку et я 0е неразличимы по Ek, а значит, и по всем Eq, q< к,

tyl(ct) = tyxitf) ,

tM) = '>а(Л

следовательно,

t^etff) = t^ct). При q = 0~aq=k+\

t^ctf?) = t^ot) +tjtf) tjjfct)= #) + t^ct). Отсюда следует t^otß1) = tjjfct), а значит, неразличимость новой пары по и немедленно

получается оценка длины полных множеств вида

к> log 2 п. Эту оценку можно улучшить. Теорема 3. Если V = Епк полно, то

к>с\од2п, с =--—

. л/5+1

'og2 —^—

Доказательство проводится построением последовательности пар длины п*

с л/5+1 =—j=(ck -1) + о(1), с =-, неразличимых по Ек.

V 5 2

Для к = 3 неразличимую пару можно построить из описанных выше с? = (01101001) и ^ = (10010110) вычеркиванием из первого слова пятой координаты, а из второго - третьей координаты,

tí* = (0110001), /? = (1000110), причем эта пара - минимальная по длине среди неразличимых по третьему слою булевского куба.

Продолжая таким же образом, т.е. склеивая ак и рк и затем вырезая из первого ot~2 (или /7е"2) сразу после середины нового слова, а из второго - непосредственно перед серединой, мы получим нужную последовательность пар векторов ct, ff, к = 1, 2, ... , длины и*. Неразличимость этих векторов является следствием доказанной ранее эквивалентности реконструкции векторов по фрагментам и решения системы диофантовых уравнений.

В § 5 рассмотрена задача Aw реконструкции по словам, то есть F-множество имеет вид

Vw(k) = {(1 2 ... к - 1 к), (2 3 ... к к + 1), ..., (п-к+\п-к + 2 ... п-\ п)}.

Пусть G - ориентированный граф, вершины которого соответствуют фрагментам, причем вершины i и j соединены ребром в том и только в том случае, когда соответствующие фрагменты а' = (а'и ..., а\) и ci = {d\,...

, dk) удовлетворяют соотношениям а'г = d\, ..., а\ = <¿k-ь a G' - соответствующий граф де Брейна, то есть ориентированный мультиграф, вершины которого -точки куба Ек.\, ребра - фрагменты, причем ребро а' = (d\, а'ъ... , dk.}, а'к) соединяет вершину (d\, а'ъ... , a'k.¡) с вершиной (d2,..., d/c-i, dk).

Утверждение. Решения задачи Aw соответствуют гамильтоновым путям в графе G.

Утверждение. Решения задачи А%у соответствуют эйлеровым путям в графе С.

В данном случае сфера и ограниченный ею шар не являются конгруэнтными множествами. Простейший пример этого - слова А] = (010) и А2 = (101), неразличимые по словам длины 2,

К(Л1)=Г(Л2)={01,10}, но различимые по словам длины 1,

У(А0 = (0, 0,1}, У(А2) = (0,1,1}.

Лемма, ^-множество Уп(к) дает возможность восстановить все фрагменты неизвестного слова л:, образованные (к- 1), тогда и только тогда, когда слово х не является периодическим с периодом (п - к + 1).

Лемма. Пусть к > п/1 и для неизвестного слова А выполняется условие {а\а% ... а-к-г а к а) ^ {р-п-к+г ап-к+1 — 1 а„). Тогда слово А восстанавливается по матрице фрагментов Ак однозначно.

Лемма. Пусть к > п/1. Если все равны между собой, 51 = 52 = ••• = Як = я, то слово А - периодическое, причем величина периода является делителем числа (п - к + 1). Два слова Г-эквивалентны в том и только в том случае, если они получаются друг из друга циклическим сдвигом.

Теорема. Пусть порождающее множество имеет вид К = {(1 2 ... к- 1 к), (2 3 ... кк+ 1), ..., (п-к+ \ п-к + 2 ... п- \ «)},

к > п/2 + 1.

Если слово А является периодическим с периодом т, делящим (п — к +1), то ^-эквивалентными ему словами являются те и только те слова, которые получаются из А циклическими сдвигами периода.

В главе П1 изучена П модель. Предполагается, что зафиксировано некоторое множество V подпоследовательностей последовательности 1, 2, ... , п. Для каждого слова а е ЕР рассматриваются только такие его фрагменты (подпоследовательности), которые порождаются множеством подпоследовательностей V. Каждая подпоследовательность V е V задана характеристическим набором (VI Уг ... таким, что V/ = 1, если I е V, и V,- = 0 в противном случае. На выходе, в отличие от I модели, получается множество, а не мультимножество, то есть для каждого слова из Ей указано только, входит ли оно в реконструируемое слово в качестве фрагмента при множестве V, но не указано, с какой кратностью оно входит.

В § 1 строится алгебраическое описание классов эквивалентности, аналогичное предыдущей главе. В данном случае основным соотношением для построения системы диофантовых представлений служит

Доказано следующее утверждение о сведении V-эквивалентности к решению диофантовых уравнений.

Утверждение. Класс эквивалентности является множеством (0,1)-решений полиномиальной системы неравенств

(Шй.-0

где ]¥а = {/,} - множество всех различных фрагментов, порожденных_характеристическим множеством V* из слова а и Жа - {у,} - дополнение (с учетом размерности соответствующих фрагментов).

В § 2 исследован вопрос о полноте V = Е„к. В отличие от I модели, во II модели этот вопрос решен полностью.

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

Теорема 4. Пусть N - множество всех различных фрагментов длины к слова х длины п. Тогда необходимым и достаточным условием того, что слово х однозначно восстанавливается по N, является условие к > я/2. При его выполнении восстановление осуществляется

за к Ы операции.

Необходимость условия очевидна, поскольку слова (0101 ... 01) и (1010 ...10) длины 2п содержат в качестве фрагментов весь куб Е„. Достаточность доказывается построением алгоритма.

При к > п/2 в наборе N не могут одновременно присутствовать 0к и 1*. Предположим, что отсутствует 0*, а значит, число нулей в слове не больше числа единиц.

Представим вектор Хе Е„ в виде

0й10А10А...0Л"10Л,+|, гдеpi,p2, ..., Pm+i ¿0- неизвестные параметры,

_{\,ieP = {px +\,рх +р2 +2,...,р{ +... + рт + Х'~\ 0 ,i£P

Пусть фрагменты из набора N упорядочены в лексикографическом порядке. Набор N распадается на непересекающиеся слои ¿о = { а: (00 ... 0) < а < (100 ... 0)}, Si = { д: (10 ... 0) < а < (110 ... 0)},

5т={а: (1... 10 ... 0) е Е™'1 :< а < ((1 ... 10 ...0) е Ект}. В ходе процедуры восстановления параметров р\, р

2> • •• } Рт+1 просмотр ведется в порядке возрастания номеров слоев и векторов внутри слоя.

1. 5о = 0. Тогдар\ ~ 0.

2. 5о Ф 0. Тогда р\ ^ 0, а в 5о входят векторы с т единицами. Пусть а*1 - наименьший из таких

векторов, а*\ = 0Ч1у, | Ш = т — 1, ц > 0.

A) Если |у| > т - 1, по определению а*\ в него входят все нули из первой серии нулей слова X, то есть р\ = д.

B) Если |г] = т - 1, а*I = 0кт\т, то р\ + т > к, следовательно, рг + рг + — + Рт+\ < к. Тогда наименьший вектор в следующем слое включает все нули слова X, расположенные после первой единицы. По этому слову восстанавливается рг + рг + ... + рт+ь а значит, определяется р\.

Пусть после просмотра слоев 5о,..., «Я; и, возможно, вектора, непосредственно следующего за «Я;, восстановлены^;, ...р,\

3. Я,- = 0. Тогдар,- = 0.

4. Я,- ф 0. Тогда р1 ф 0, а в 5/ входят векторы с т единицами. Пусть <2*1 - наименьший из таких

векторов, а*1 = 1'о91у, | \т\ | — т - г - 1, # > 0.

A) Если У > т - / - I, по определению а*\ в него входят все нули из 1-й серии нулей слова X, то есть =

B) Если У = т - 1, а*\ = 1?0^ т1т \ тор&\ +'... + рт+\ < к. Тогда наименьший вектор в следующем слое

включает все нули слова X, расположенные после г-й единицы. По этому слову восстанавливаетсяр\+\ + ... + рт+ь а значит, определяется

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

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

В § 3 рассмотрены оценки длины реконструирующих фрагментов при ограниченном числе серий в слове.

Лемма. Пусть слово я: длины и с то нулями и т\ единицами состоит из р > 1 серий, причем длина второй по величине серии равна Тогда слово х однозначно восстанавливается по фрагментами длины I = (р + я - 1).

В алфавите из 2 символов среднее число серий равно и/2, то есть содержит все фрагменты длины и/4, поэтому отличие средней длины реконструирующих фрагментов от и/2 невелико. Если число символов в алфавите велико, ситуация меняется: средняя длина серий сильно уменьшается, а число серий растет значительно медленнее. Этот случай рассмотрен в § 4.

Пусть алфавит состоит из / символов 0, 1, ...,(/- 1). В этом случае среднее число серий из каждого символа и/-и + 1 и

равно ——--у, а среднее число вхождении символа

п

в слово равно —, поэтому и для нахождения серии

конкретного символа оказывается достаточно фрагментов с длиной порядка у символов.

Утверждение. Для однозначного восстановления слова а из Е„(Г) достаточно фрагментов длины Ь, удовлетворяющей двум условиям:

а) Ь > (т1 +Р1-1)/2 для всех / = 0,1,..., (/-1);

б) Ь > 2(р{ + р]) -1 для всеху = 0,1,... ,(/-1).

В § 5 рассмотрена задача распознавания по подсловам во П модели. Построены тесты, позволяющие различать пары слов.

Глава IV посвящена частным случаям К-множеств, имеющим важные практические применения в кодировании и распознавании образов.

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

В случае, когда длина фрагментов к больше

половины длины слова, ^-множество Е* является сильно избыточным. Получены оценки необходимого и достаточного числа фрагментов для реконструкции при (п-к) «п.

Лемма. В случае, если к > 1пП\ + 1, для любого слова а длины п существует множество V, включающее {.п/2} + 1 окон, для которого У(а) * 7(0) при любом

Рассмотрены 2 задачи. В обоих случаях информация о неизвестном векторе - набор длинных фрагментов, получаемых выпадением из вектора я = пк элементов. В первой задаче известен набор окон V и фактически требуется определить, какое окно

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

В случае известного набора окон при к = п - 1 произвольные три окна, очевидно, обеспечивают однозначное восстановление вектора по фрагментам; восстановление осуществляется по мажоритарному правилу. При к = п - 2 в общем случае для однозначности недостаточно (2п - 3)-х фрагментов. Использование дополнительных ограничений на кратность p(i) вхождения элементов в множество / меняет ситуацию.

Теорема. Пусть / = { (/ь jx), (z2, /2), Оз. Уз) } и для всех i е 1 кратность p(i) ~ 1. Тогда / - полное множество.

Теорема. Пусть 7= {(h.ji), (h J2), - , (is.js)} и p(i) <2 для всех i ei. Тогда I- полное множество. Приp(i) < 3 для однозначного восстановления достаточно восьми фрагментов.

Если окна не фиксированы, т(п, п - 1) = [ п/2 ] + 2.

Для случая коротких фрагментов, рассмотренного в § 2, и ограниченного набора возможных слов А, \ А | = q, исследована задача о минимальной мощности V-множества, обеспечивающего корректное распознавание слов из этого набора. Доказано, что мощность минимального множества - (q - 1). Доказательство основано на представлении слов элементами ультраметрического пространства. Задача о построении этого множества сведена к построению остовного дерева в графе определенного вида. Для случая, когда отбор

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

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

Математическая морфология, рассмотренная в § 3, соответствует случаю 7-множеств из стандартных малых фрагментов, как правило, достаточно простой формы. Эти фрагменты задают структурирующие элементы -основное понятие математической морфологии. Разработанные методы анализа фрагментарных представлений дают возможность строить описания форм, в том числе и многомерных, в терминах «спектра образов», полученных в ходе операции открытия со структурирующими объектами в форме шаров возрастающего радиуса. Для отбора Г-множеств в конкретных задачах предложено использовать генетический алгоритм и нейронную сеть Хэмминга.

Для сопоставления полученных спектральных представлений с эталонными также применен вариант рандомизированного алгоритма из § 6 гл. I.

В стеганографии (§ 4) К-множества описывают кодовые блоки. Цель стеганографии - передача зашифрованной информации таким образом, чтобы непосвященный перехватчик не мог даже догадаться о наличии скрытой информации. Идея заключается в использовании некоторого открытого носителя информации, на отдельных участках которого производятся изменения, незаметные для постороннего наблюдателя, но несущие информацию владельцу секретного ключа. Пусть передаваемое слово а - (а\ а„), а разбиение на блоки производится с помощью множества

то есть блоки -

<аУ >={а\,...а\^,...,<а,ут >=(<,...<■).

Секретные параметры алгоритма, известные только отправителю и получателю:

а) Г-множество, разбивающее а на блоки определенной длины;

б) правила преобразования блока с целью внесения скрытой информации;

в) функция от символов блока, содержащая скрытую информацию.

Пусть Г-множество разбивает слово на блоки одинаковой длины п, функция преобразования -линейная комбинация символов блока с коэффициентами

п

.. , и'„), функция выхода Е = У^ Ща, (гооёТ?) , где

R = ехр2Г <n. Требуется выбрать n,R и w,- таким образом, чтобы можно было получить любое значение 2 е (О, R -1) при заданных ограничениях на допустимые изменения символов блока.

Для передачи скрытого слова длины п, являющегося двоичной записью числа 2* = 2 + Д, требуется изменить значения битов щ:

а,* = щ + 8/ (mod 2), 5,- е {0,1}, таким образом, чтобы

я

Ограничения связаны с числом Ô компонент 5/, отличающихся от 0.

Следовательно, задача проверки допустимости выбора параметра R и ограничения m сводится к проверке существования решения диофантова уравнения

п

^ wtxt = A (modi?)

¿=i

при любой правой части во множестве двоичных векторов с малым числом единиц, | M |< 8.

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

Глава V посвящена задачам, в которых однозначная реконструкция невозможна, и требуется описать классы F-эквивалентных слов. Эта задача концептуально близка к задачам распознавания. Для ее решения предложено использовать конкретный вид динамических систем -обучающиеся системы, сходные с нейронными сетями, с неархимедовыми числовыми полями и операциями из разных алгебр.

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

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

В § 1 проведен анализ общих принципов работы нейронных сетей и их недостатков с точки зрения задач реконструкции слов.

В § 2 проведено исследование пригодности различных нейросетевых моделей для решения задач реконструкции. Рассмотрены модели с обучением на основе проецирования на выпуклые множества, морфологические нейронные сети и нейронные сети в операциях (х, min).

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

Последние параграфы посвящены методам устранения известных недостатков нейронных сетей -

возможности ложных решений и ограниченной емкости их памяти.

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

Х={хке (- 1, 1)"}, к=\,...,г,г«8 = 2".

Для него определяется множество выходных векторов

У={ук = Итп^[А\хк)}}.

Тогда

Рг = е & ЩпеЦу),Т) =0 & Щ;) > 4

Я

} =

1-1У

„с . Ч у

"(Кг)

и при г = д°1п{д(1), й> с

Рг < 0(де) ВД(1 - яс У"|п? = 0(яЧ =

= 0(\пд / да~с). При больших д эта величина меньше 1/2, и тест можно использовать в алгоритме типа Лас-Вегас. Повторяя тестирование с другими случайными ¿хЬдными векторами, можно получить, что со сколь угодно близкой к единице вероятностью центрами достаточно больших

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

Процедуры устранения ложных решений различны для разных нейросетевых моделей.

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

ВЫВОДЫ

В диссертации представлены следующие основные результаты.

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

2. Сформулированы основные модели восстановления слов по их фрагментарным представлениям.

3. Доказана алгоритмическая сложность рассматриваемых задач реконструкции.

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

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

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

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

8. Изучена связь задач реконструкции слов с нейронными сетями в неархимедовых числовых полях. Описаны нейросетевые "модели такого вида, полезные в задачах реконструкции слов. Предложены методы повышения эффективности работы нейронных сетей: а) алгоритм класса Лас-Вегас для обнаружения и устранения некорректных решений; б) алгоритм повышения емкости нейронной сети за счет перекодировки входных векторов.

Основное содержание диссертации опубликовано в работах:

1. Леонтьев В.К., Сметанин Ю.Г. О восстановлении слов по фрагментам. // Всесоюзная конференция "Математические методы распознавания образов", г. Дилижан. -1985 г. - С.112 -114.

2. Сметанин Ю.Г. Классификация изображений методом подсчета числа характерных конфигураций. // Тезисы докладов 2-й Всесоюзной конференции "Методы и

средства обработки графической информации", г. Горький. - 1985 г. - С. 73 - 74.

3. Сметанин Ю.Г. Об алгебраической сложности задач восстановления векторов. Деп. рукопись. Указатель ВИНИТИ 6643 - В86 от 03.09.1986 г.

4. Сметанин Ю. Г., Хачиян Л.Г. Применение псевдополиномиальных алгоритмов для некоторых задач комбинаторной оптимизации с ограничениями. // Изв. АН СССР. Тех. Кибернетика. - 1986, № 6.

5. Сметанин Ю. Г. О некоторых задачах восстановления слов по фрагментам: Дис. ... канд. физ.-мат. наук. М., 1986.

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

7. Сметанин Ю. Г. Распознавание при представлении исходных данных в виде длинных последовательностей. // Распознавание, классификация и прогноз. Математические методы и их применения. - Вып. 2. - М.: Наука. - 1988. - С. 38 -41.

8. Leont'ev V. К., Smetanin Yu. G. Restoration of Finite Integer Sequences Given a Set of It's Subsequences. // 1st Int. Conf. on Information Technologies for Image Analysis and Pattern Recognition ITIAPR'90. - October 1990, Lviv, USSR. - P. 196 - 200.

9. Smetanin Yu. G. Representation of a Long Sequence with Its Component Short Sequences. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - 1991. - Vol. 1, № 2. P. 195 - 199.

10. Smetanin Yu. G. A Monte-Carlo Algorithm for Matching

the Images Represented by Sets of Fragmentary Features.

---- -

Г'-'- <Ш1ЬЙАЯ

6'П.;Й0ТЕКА С. Петербург 2С0 РК

// Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. // 1993. - Vol. 3, ЖЗ.-Р. 285-288.

11. Smetanin Yu. G. Random Sampling in the Estimation of the Number of Attraction Basins in Neural Networks. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - 1994. - Vol. 4, №. l.-P. 74-77.

12. Smetanin Yu. G. A Las Vegas Method of Region of Attraction Enlargement in Neural Networks. // The International Society for Optical Engineering, Bellingham. SPIE. - 1994. - Vol. 2363. - P.. 77 - 84,104 -108.

13. Smetanin Yu. Neural Networks as Systems for Pattern Recognition: A Review. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - 1995. - Vol. 5, №. 2. - P. 254 - 293.

14. Smetanin Yu. A Neural Network for Determining Shortest Paths in a Graph. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - 1995. - Vol. 5, № 3. - P. 376 - 378.

15. Smetanin Yu. G., Khilkov A. V. The Study of Efficient Computability and Readability of the Morphological Framework of Image Analysis in the Class of Self-Organizing Neural Networks // Pattern Recognition and Image Analysis. - 1997. - Vol. 7, № 2. - P. 283 - 287.

16. Сметании Ю. Г. О числе фрагментов, обеспечивающих однозначное восстановление неизвестного двоичного слова. // Труды Четвертой Всероссийской с международным участием конференции «Распознавание образов и анализ

изображений: новые информационные технологии», г. Новосибирск, 11-18 октября 1998 г. - С. 174 - 178.

17. Smetanin Yu. G. Neural Networks as Systems for Pattern Recognition. // Journal of Mathematical Science. Kluwer Academic/Consultants Bureau, New York. - 1998. - Vol. 89, №. 4.-P. 1406- 1457.

18. Smetanin Yu. G. On the Number of Vectors Necessary for the Unique Reconstruction of Unknown Vectors. // Collection of Abstracts of the 5th Open German-Russian Workshop on Pattern Recognition and Image Understanding:, September 21 - 25, Herrsching, Germany. - 1998. - 4 pp.

19. Leont'ev V. K., Smetanin Yu. G. Problems of Information on the Set of Words. // Journal of Mathematical Sciences. Kluwer Academic/Consultants Bureau, New York, 2000. - P. 49 - 70.

20. Smetanin Yu. G. Refined Logarithmic Bound for the Length of Fragments Ensuring the Unambiguous Reconstruction of Unknown Words. H Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. - 2001.- Vol. 11,№ l.-P. 100- 102.

21. Leont'ev V. K., Smetanin Yu. G.. Recognition Model with Representation of Information in the Form of Long Sequences. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. -2002. - Vol. 12, No. 3. - C. 250 - .

Утверждено к печати Вычислительный центр им. А.А. Дородницына Российская Академия Наук

Формат 60 х 84 1/16. Тираж 100 экз. Объем 1.7 п.л. Заказ № 7 Участок оперативной полиграфии ИЭиА РАН 177334, Москва, Ленинский проспект 32А

РНБ Русский фонд

2007-4 15020

\

1 s »î'«P ?0M

Введение

Обозначения и определения

Глава I. Комбинаторика слов и задачи реконструкции

§ 1. Основные направления исследований в комбинаторике слов и задачи синтеза слов

§ 2. Формулировка задач реконструкции слов

§ 3. Алгоритмическая сложность задач реконструкции слов

§ 4. Независимость полноты F-множеств от алфавита

§ 5. Сжимающие классы и конгруэнтность Vмножеств

§ 6. Псевдополиномиальные алгоритмы поиска решений в задачах реконструкции слов

Глава И. Первая модель реконструкции

§ 1. Алгебраическое описание классов эквивалентности

§ 2. Полнота характеристических множеств

§ 3. Верхняя граница длины к для полных V множеств Еп

§ 4. Нижняя граница длины к для полных V множеств Епк

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

Глава III. Вторая модель реконструкции

§ 1. Алгебраическое описание классов эквивалентности

§ 2. Полнота V-множеств Епк

§ 3. Реконструкция слов с малым числом серий

§ 4. Вторая модель реконструкции в случае многозначного алфавита

§ 5. Распознавание по полсловам

Глава IV. ^-реконструкция в кодировании и распознавании образов

§ 1. Реконструкция по длинным фрагментам

§ 2. Распознавание по коротким фрагментам

§ 3. Двумерная F-реконструкция и математическая морфология

§ 4 F-множества в стеганографии

§ 5. Нейросетевые модели для реализации алгоритмов реконструкции слов

§ 6. Нахождение и устранение ложных решений в нейронных сетях

§ 7. Повышение емкости нейронных сетей с безошибочным обучением

Диссертация посвящена задачам восстановления полной информации по ее частичным описаниям. Для представления информации используются слова над конечным алфавитом. Под частичным описанием понимаются наборы слов, получаемых из неизвестных исходных слов при выпадениях части символов. Изучена связь реконструкции слов с другими задачами алгебраической комбинаторики слов. Разработаны эффективные методы реконструкции для разных типов входной информации. Описаны соотношения между характером имеющейся частичной информации и достижимой точностью реконструкции или г возможностью определения характеристик слов, описанных этой информацией; определены условия однозначной реконструкции слов по частичной информации. Подробно изучены две задачи реконструкции: по мультимножеству всех фрагментов заданной длины и по множеству всех фрагментов заданной длины. Определены границы длины фрагментов, при которой реконструкция однозначна. Получены оценки эффективности предложенных методов реконструкции.

Теория реконструкции слов возникла в результате интеграции Я* алгебраической комбинаторики слов с методами теории кодирования и распознавания образов. Спецификой теории реконструкции как раздела комбинаторики слов является ее основная задача: синтез слов по частичным представлениям, впервые сформулированная в работах В.К.Леонтьева [21, 35, 36, 39].

Комбинаторика слов

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

Историю комбинаторики слов можно вести от работ А. Туэ в начале XX века [255, 256], однако становление ее как самостоятельной дисциплины относится ко второй половине 80-х гг. XX века. Главной целью разработчиков новой области [5, 190, 191] является изучение слов как самостоятельного объекта с точки зрения их внутренней структуры. Многие важные результаты по комбинаторике слов были открыты в теории чисел, теории групп, теории вероятностей, кодировании. Используемые методы определялись в первую очередь спецификой этих областей. Создание комбинаторики слов как особой области способствует взаимопроникновению различных методов и созданию новых подходов к решению возникающих задач.

В качестве примеров такого взаимопроникновения можно привести лемму о периодичности Файна - Уилфа [145], алгоритм Маканина [42] и свойство компактности свободных моноидов [83].

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

Фундаментальный результат Маканина о разрешимости уравнений в свободных полугруппах непосредственно применим в комбинаторике слов, но в теории групп он был осознан как чисто теоретический, фактически как теорема существования. Практическое значение он получил именно в теории слов после того, как был предложен алгоритм решения уравнений в словах, принадлежащий классу PSPACE [219].

Свойство компактности возникло уже в рамках собственно теории слов. Оно показывает, что любая независимая система над свободным моноидом с конечным числом неизвестных является конечной. Поиск верхней границы мощности независимых систем (до сих пор остающейся неизвестной [172]) является важным и интересным направлением дальнейших исследований.

Детальный обзор задач и методов комбинаторики слов представлен в [191].

Задачи комбинаторики слов, связанные с реконструкцией

Задачи реконструкции слов тесно связаны с задачами кодирования [3, 25, 29, 30, 31, 32, 44, 49, 76, 79], распознаванием образов [17, 21, 35, 88, 97, 166], символьным анализом динамических систем [84, 85, 177, 209, 210], конечными автоматами [12, 89, 157, 243], молекулярными вычислениями, анализом последовательностей протеинов и комбинаторным синтезом ДНК [82, 199,213,231,264].

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

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

Анализ последовательностей ДНК и протеинов - область активного применения методов комбинаторики слов, являющаяся предметом многих междисциплинарных проектов.

Среди результатов, непосредственно связанных с темой данного исследования, следует выделить:

- формулировку метрических задач в «-мерном булевском кубе [38] и задач восстановления слов по фрагментам, полученным с помощью фиксированных правил [36],

- оценки спектров бинарных слов [37],

- оценку максимальной длины цепи в булевом кубе и длины надпоследовательности для множества слов из заданного слоя булева кода [14, 15],

- условия реализуемости матриц расстояний в единичных кубах [1],

- методы покрытия множества слов цепями [47] и покрытия графов маршрутами [48],

- методы описания слов, содержащих все подмножества как подслова [188, 259], и слов, содержащих наименьшее число различных подслов [130],

- перечисление вполне монотонных семейств слов [211],

- меры сложности подпоследовательностей [192],

- методы восстановления объектов по минимальному числу слабо искаженных образцов [32].

Для решения задач анализа слов, в различной мере связанных с реконструкцией, применялись:

- метрические методы в n-мерном кубе [38,64],

- методы автоматического анализа сложности слов [241],

- различные подходы к упорядочению двоичных слов [109],

- теория Шпернера в частично упорядоченных множествах

143],

- конструкции кодов Грея [52],

- методы анализа периодичности слов с помощью нейронных сетей [16].

Место задач реконструкции в комбинаторике слов

Большинство перечисленных задач и подходов к их решению связано со структурным анализом слов и описанием их классов. Задаче синтеза слов по частичным представлениям, естественно возникающей в большинстве прикладных задач, уделялось значительно меньшее внимание, и существенных результатов в этом направлении значительно меньше. Сложность задач реконструкции отмечалась многими авторами [36, 89,196].

Относительно простым частным случаем рассматриваемой проблемы является реконструкция по подсловам [61, 62], которой посвящено большинство известных работ по реконструкции слов. При более сложных правилах получения частичных представлений известны только методы, использующие дополнительную информацию о возможных положениях искажений и потерь информации. К ним относятся известные методы реконструкции алгебраических функций по данным с пропусками [89], реконструкции компактных многомерных многообразий по набору расстояний между парами точек из заданного набора [152], нахождения распределения случайной величины или параметров т марковских случайных процессов по частичной информации [1, 2, 4], представления конечных автоматов фрагментами поведения [12].

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

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

Формальная постановка задачи реконструкции

Пусть задано множество ЕР слов длины п. Предполагается, что зафиксировано некоторое множество V подпоследовательностей последовательности {1, 2, . , п). Для каждого слова а е ЕГ рассматриваются только такие его фрагменты (подпоследовательности), которые порождаются множеством

1 АI подпоследовательностей V = {v v . v }. Каждую подпоследовательность из V можно считать каналом с искажениями. Подпоследовательность vr е V задана характеристическим набором (У) vr2 . таким, что v, = 1, если й символ слова входит во фрагмент, полученный с помощью V, и v, = 0 в противном случае.

Процедура получения из слова а фрагмента с помощью характеристического вектора v = ^у--^1''2описывается в виде операции фрагментирования <а, v> = {afah.aik). При получении фрагмента Ъ е £ неизвестно, от действия какого именно характеристического вектора на исходное слово получен этот фрагмент.

В данной формулировке задачи вся информация о слове х е £", полученная на выходе канала V, заключается в мультимножестве или множестве F(x). Требуется определить, насколько полно эта информация определяет исходное слово х <=Е".

Сложность задачи реконструкции

Сложность рассматриваемой задачи видна из следующего доказанного результата об NP-полноте задачи о существовании реконструируемого слова уже при коротких подпоследовательностях. Даны: целое число я, характеристическое множество V = {уь . , vm}, v, е Еп, I v, |= 3, i = 1, 2, . , m, и набор векторов Ь.еЕ3 ,j = 1, 2, . , m\ требуется определить, являются ли векторы bj фрагментами некоторого вектора длины я, то есть существует ли вектор Ь е Еп такой, что для некоторой перестановки выполняются равенства

J\J2--Jmj b, V/> = bji, i= 1,., т.

Как непосредственное следствие, доказана NP-полнота задачи о единственности реконструируемого слова.

Эти результаты говорят о нецелесообразности поиска универсального метода реконструкции. Поэтому далее рассмотрены конкретные виды F-множеств.

Зависимость от алфавита в задачах реконструкции

Множество V разбивает Е" на классы эквивалентности; в один класс попадают те слова, у которых множества фрагментов, полученных с помощью совокупности правил К, совпадают. Если каждый класс эквивалентности состоит из одного вектора, множество V называется полным.

Следующее утверждение показывает, что в задачах однозначной реконструкции можно ограничиться случаем двоичного алфавита: если множество V является полным на двоичном кубе Еп, то оно является полным и на любом г-значном кубе Еп(г), г = 3, 4, . . Эта эквивалентность позволяет описывать классы эквивалентности при заданном правиле V определенной булевской функцией - теоретико-множественным перманентом.

Две основные модели реконструкции

Подробно изучены два наиболее важных и интересных класса задач реконструкции в случае, когда F-множество является к-м слоем куба Е?. В первой модели входной информацией является мультимножество фрагментов, во второй модели - множество фрагментов (без учета кратности).

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

В первой модели получены уточнения границы величины к:

1 /О

C\logn<k<C2n .

Во второй модели получена точная оценка длины к фрагментов, при которой обеспечена однозначность восстановления произвольного слова длины п: к = 1и/2 J + 1.

Частные случаи V-множеств и их применения

Получены оценки необходимого и достаточного числа фрагментов для реконструкции при (п - к) « п. Эти оценки использованы для построения алгоритмов коррекция ошибок для многих приемников.

Для случая коротких фрагментов и ограниченного набора возможных слов А, \ А \ = q, исследована задача о минимальной мощности F-множества, обеспечивающего корректное распознавание слов из этого набора. Доказано, что мощность минимального множества - (q - 1). Доказательство основано на представлении слов элементами ультраметрического пространства. Задача о построении минимального множества сведена к построению остовного дерева в графе определенного вида.

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

Для реализации восстановления по фрагментам, соответствующим известным окнам, применяется вариант нейронной сети с обучением на основе проецирования на выпуклые множества.

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

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

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

Предложены также обобщенные варианты морфологических нейронных сетей [90, 91, 229, 230] и нейронных сетей на основе алгебр Клиффорда [94] для практической реализации предложенных вариантов математической морфологии и распознавания на основе инвариантов.

Нейронные сети в неархимедовых числовых полях использованы для анализа информативности F-множеств.

Содержание диссертации по главам

Диссертация состоит из Введения и четырех глав.

1. Алексейчук А. Н. Об однозначности проблемы моментов в классе-распределений // Дискретная математика. 1998. - Т. 10, вып.1.-С. 95-110.

2. Алексейчук А. Н. Условия однозначности проблемы моментов вклассе ^-распределений. // Дискретная математика. 1990. - Т.1.,вып. 4.-С. 48-57.

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

4. Басманов А. Е., Дикарев В. А. Синтез стохастической матрицы посистеме ее фрагментов. // ХТУРЭ, Харьков. 1997. - 8 с.

5. Белов А. Я., Борисенко В. В., Латышев В. Н. Мономиальныеалгебры. // Итоги науки и техники. Современная математика и ее приложения. Тематические обзоры. М.: 2002 - Т. 26. - С. 35 -214.

6. Бенуа-Пиньо Ж., Хренников Ю., Котович Н. О сегментацииизображений в р-адической и евклидовой метриках. // ДАН СССР. 2001. - Т. 381, № 5. - С. 604 - 609.

7. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир,1971.477 с.

8. Боревич 3. И., Шафаревич И. Р. Теория чисел. М.: Наука,1985.504 с.

9. Ван дер Варден. Алгебра. М.: Наука, 1976. 624 с.

10. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1967. 574 с. П.Горелик Ф. П., Скрипкин В. А. Методы распознавания. М.:Высшая школа, 1984. 208 с.

11. Грунский И. С., Козловский В. А., Пономаренко Г. Г. Представление конечных автоматов фрагментами поведения. Киев: Наукова думка. 1990. 232 с.

12. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

13. Евдокимов А. А. О максимальной длине цепи в единичном п-мерном кубе. // Мат. Заметки. 1969. - Т. 6, № 3. - С. 309 - 319.

14. Евдокимов А. А., Ню В. Длина надпоследовательности для множества двоичных слов с заданным числом единиц. // Методы дискретного анализа в теории графов и сложности: Сб. науч. тр. Новосибирск: Ин-т математики СО РАН. 1992. - Вып. 52. - С. 49-58.

15. Ежов А. А., Чечеткин В. Р. Выделение скрытых периодичностей в зашумленных последовательностях символов с помощью нейронной сети. // Математическое моделирование. 1998. - Т. 10, №3.-С. 83-92.

16. Журавлев Ю. И. Об оптимальных алгоритмах выбора. // Докл. Акад. Наук СССР. 1959. - Т. 121, № 3. - С. 411 - 414.

17. Журавлев Ю. И. Об алгоритмах упрощения дизъюнктивных нормальных форм. // ДАН СССР. 1960. - Т. 132, № 2. - С. 260 -263.

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

19. Зимин А. И. ??? // Математический сборник. 1984.- 37.- С. 353-364.

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

21. Карацуба А. А. Основы аналитической теории чисел. М.: Наука, 1983.

22. Касасми Т., Токура Н., Ивадари Ё., Инагаки Я. Теория кодирования. М.: "Мир", 1978. 576 с.

23. Коблиц Н. р-адические числа, р-адический анализ и дзета-функции. М.: Мир, 1982. 192 с.

24. Коршунов А. Д. О числе бинарных слов с заданной длиной максимальной серии. I. // Дискретный анализ и исследование операций. 1997. - Т. 4, № 4. - С. 13 - 46.

25. Косточка А. В., Мазуров В. Д., Савельев Л. Я. Число ^-ичных слов с ограничениями на длину максимальной серии. // Дискретная математика. 1998. - Т. 10, вып. 1. - С. 10. 19.

26. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Докл. АН СССР. 1965. Т. 163, №4. С. 707-710.

27. Левенштейн В. И. О совершенных кодах в метрике выпадений и вставок. // Дискретная математика. 1991. - Т. 3, вып. 1. - С. 3 -20.

28. Левенштейн В. И. Элементы теории кодирования. // Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974.-С. 207-305.

29. Левенштейн В.И. Восстановление объектов по минимальному числу искаженных образцов. // Докл. РАН. 1997.- Т. 354, №5.-С. 593-596.

30. Ленг С. Алгебра. М.: "Мир". 1968. - 564 с.

31. Леонтьев В. К. Дискретные экстремальные задачи. // Итоги науки и техники. 1979. - Т. 16. - С. 39 - 101.

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

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

34. Леонтьев В. К. О спектрах бинарных слов. // Методы комбинаторной оптимизации. М.: ВЦ РАН. 1997. - С. 37 - 46.

35. Леонтьев В.К. О некоторых метрических задачах в «-мерном кубе. // Журнал вычислительной математики и математической физики. 2002. - 41, № 2. - С. 251 - 257.

36. Леонтьев В.К., Сметанин Ю.Г. О восстановлении слов по фрагментам. // Всесоюзная конференция "Математические методы распознавания образов", Дилижан, 16-21 мая 1985. С. 112-114.

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

38. Майника Э. Алгоритмы оптимизации на сетях и графах. М.: Мир. 1981.

39. Маканин Г. С. Проблема разрешимости уравнений в свободной полугруппе. Математический сборник. 1981. - № 32. - С. 129 -198.

40. Маканин Г.С. Уравнения в свободных группах // Изв. АН СССР. Сер. мат. 1982. - Т. 46, N 6. - С. 1199 - 1274.

41. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. Теория кодов, исправляющих ошибки. М.: "Связь", 1979. 744 с.

42. Матерон Ж. Случайные множества и интегральная геометрия. М.: Мир. -1978.

43. Методы компьютерной обработки информации. Под ред. Сойфера В. А. М.: Физматлит, 2001. 780 с.

44. Ню В. Покрытие множества слов цепями: Дис. . канд. физ.-мат. Наук. Новосибирск, 1990.

45. Ню В, Евдокимов А. А. Покрытие графов маршрутами. // Методы дискретного анализа в оптимизации управляющих систем: Сб. Науч. тр. Новосибирск: Ин-т математики СО АН СССР. 1983. - Вып. 40. - С. 72 - 86.

46. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: "Мир", 1976. 594 с.

47. Понтрягин JI. С. Непрерывные группы. М.: "Наука". 1973. -519 с.

48. Постников А. Г. Введение в аналитическую теорию чисел. М.: Наука, 1971. 420 с.

49. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1970. 478 с.

50. Рудаков К. В. Об алгебраической теории универсальных и локальных ограничений для задач классификации. // Распознавание, классификация, прогноз. М.: Наука. - 1989. -С. 176-201.

51. Рыков В.В., Дьячков А.Г. Об одной модели ассоциативной памяти. // Проблемы передачи информации. 1988.- Т. XXIV. Вып. З.-С. 107-110.

52. Сметанин Ю.Г. Классификация изображений методом подсчета числа характерных конфигураций. // Тезисы докладов 2-й Всесоюзной конференции "Методы и средства обработки графической информации", г. Горький. 1985 г. - С. 73 - 74.

53. Сметанин Ю.Г. Об алгебраической сложности задач восстановления векторов. Деп. рукопись. Указатель ВИНИТИ 6643-В86 от 03.09.1986 г.

54. Сметанин Ю. Г. О некоторых задачах восстановления слов по фрагментам: Дис. канд. физ.-мат. наук. М., 1986.

55. Сметанин Ю. Г. Распознавание при представлении исходных данных в виде длинных последовательностей. // Распознавание, классификация и прогноз. Математические методы и их применения. Вып. 2. - М.: Наука. - 1988. - С. 38 - 41.

56. Сметанин Ю. Г., Хачиян Л.Г. Применение псевдополиномиальных алгоритмов для некоторых задач комбинаторной оптимизации с ограничениями. // Изв. АН СССР. Тех. Кибернетика. 1986, № 6.

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

58. Сметанич Я. С. О восстановлении слов. // Тр. Мат. ин-та им. В. А. Стеклова. М.: Наука, 1973. Т. 83. - С. 183 - 202.

59. Татт У. Теория графов. М.: Мир, 1988. 424 с.

60. Тылкин М. Е. О реализуемости матриц расстояний в единичных кубах. // Проблемы кибернетики. 1962. - Вып. 7. - С. 31 - 42.

61. Улам С. Нерешенные математические задачи. М.: Наука, 1964. с.

62. Уфнаровский В. А. Комбинаторные и асимптотические методы в алгебре. // Итоги науки и техники. Современные проблемы математики. Фундаментальные направления. М.: ВИНИТИ, 1990. - Т. 56. Алгебра 6. - С. 5 - 177.

63. Уфнаровский В. А. О правильных словах в смысле Ширшова. // Межд. конф. по алгебре. Тез. докл. по теории колец, алгебр и модулей. Новосибирск. 1989. С. 140.

64. Харари Ф. Теория графов. М.: Мир, 1973. 300 с.

65. Харари Ф., Палмер Дж. Перечисление графов. М.: Мир, 1977. 325 с.

66. Холл М. Комбинаторика. М.: Мир, 1970. 424 с.

67. Хорн Р., Джонсон Ч. Матричный анализ. М.: Мир, 1989. 655 с.

68. Хьюитт Э., Росс К. Абстрактный гармонический анализ. М.: Наука, 1976. Т.1. 654 с. Т. 2. 901 с.

69. Чернов В.М. О линейной разделимости классов в неархимедовых замыканиях дискретных пространств. // Тезисы докладов 9-й Всероссийской конференции "Математические методы распознавания образов" (ММРО-9). 1999. - С. 124 - 125.

70. Чернов В. М., Bayro-Corrochano Е. Клиффордовы модели преобразования изображений // 3 Российская конференция по распознаванию образов и анализу изображений (РОАИ-97), Н.Новгород. 1997. - Ч. 1. - С. 291 - 295.

71. Чернов В. М., Шабашев А.В. Выделение р адических признаков из текстурных изображений // 3 Российская конференция по распознаванию образов и анализу изображений (РОАИ-97), Н.Новгород. - 1997. - Ч. 1. - С. 300 - 304.

72. Шеннон К. Работы по теории информации и кибернетике. М.: Мир.- 1963.-829 с.

73. Ширшов А. И. О кольцах с тождественными соотношениями. // Мат. сб. 1957. - 43, № 2. - С. 277 - 283.

74. Ширшов А. И. Кольца и алгебры. М.: Наука. - 1984. - 144 с.

75. Шишов А. М. О реберных кодах с нечетными расстояниями. // Методы дискретного анализа. Новосибирск. - 1982. - № 38. -С. 81-87.

76. Яблонский С. В. Функциональные построения в /-значной логике. // Тр. Матем. ин-та АН СССР. 1958. - Т. 51.

77. Ященко В. В. (ред.). Введение в криптографию. // М.: МЦНМО -ЧеРо. 1998. - 272 с.

78. Adleman L. On Constructing a Molecular Computer. In: Lipton R. J., Baum E. В., eds. DNA Computers: Processing of a DIMACS Seriesin Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 1996. - C. 1-21.

79. Albert M. H., Lawrence J. A Proof of Ehrenfeucht's Conjecture. // Theoret. Comput. Sci. 1985. - Vol. 41. - P. 121 - 123.

80. Albeverio S., Khrennikov A., Kloeden P. Memory Retrieval as a p-adic Dynamical System. Biosystems. - 1999. - Vol. 49. - P. 105 -115.

81. Albeverio S., Khrennikov A., Tirozzi B. p-adic Dynamical Systems and Neural Networks. // Mathrmatical Models and Methods in Applied Sciences. 1999. - Vol. 9, No. 9. - P. 1417 - 1437.

82. Allouche J.-P. Sur la complexite des suites infinies. // Bull. Belg. Math. Soc. Simon Stevin. 1994. - Vol. 1. - P. 133 - 143.

83. АН M. К. M., Kamoun F. Neural Network for Shortest Path Computation and Routing in Computer Networks. // IEEE Trans. On Neural Networks. 1993. - Vol. 4, № 4. - P. 941 - 954.

84. Apostolico A., Atallah M. J. Compact Recognizers of Episode Sequences. // Information and Computation. 2002. - Vol. 174. - C. 180- 192.

85. Ar S., Lipton R. J., Rubinfeld R., Sudan M. Reconstructing Algebraic Functions from Missed Data. // SIAM J. Comput. 1998. - Vol. 28, №2.-P. 487-510.

86. Arai K., Nakano R. Stable Behavoor in a Recurrent Neural Network for a Finite State Machine. // Neural Networks. 2000. - 13. - C. 667 -680.

87. Araujo F., Ribeiro В., Rodrigues L. A Neural Network for Shortest Path Computation. // IEEE Trans. On Neural Networks. 2001.-Vol. - 12, № 5. P. 1067- 1073.

88. Araujo С. P. S., Ritter G., Morphological neural networks and image algebra in artificial perception systems. // Proceedings of SPIE. -1992. Vol. 1769. - P. 128 - 142.

89. Bandt C. Self-Similar Sets. V. Integer Matrices and Fractal Tilings of Rn. I I Proc. Amer. Math. Soc. 1991. - Vol. 112. - P. 549 - 562.

90. Baram Y. On the Capacity of Ternary Hebbian Networks. // IEEE Trans, on Information Theory. 1991.- Vol. 37, №. 3.- P. 528 -531.

91. Bayo-Corrochano E. J. Geometric Neural Computing. IEEE Transactions on Neural Networks. - 2001. - Vol. 12, № 5. - P. 968 -983.

92. Beal M.-P., Perrin D. Symbolic Dynamics and Finite Automata. In: Rozenberg G., Salomaa A. (eds.). Handbook of Formal Languages. -1997. Vol. 2.-P. 463-503.

93. Bergholtz M., Johannesson P. (eds.). Natural Language Processing and Information Systems: 6th International Conference on Applications of Natural Language to Information Systems, NLDB 2002. Stockholm, Sweden, June 27-28, 2002. - Revised Papers

94. Becker P.W. Recognition of Patterns Using the Frequences of Occurence of Binary Words. Springer Verlag, Wien New York, 1978.-222 pp.

95. Berstel J. Recent Results on Sturmian Words. In: Dassow J., Salomaa A. (eds.). Developments in Language Theory II. World Scientific, Singapore. 1996. - P. 13 - 24.

96. Berstel J., De Luca A. Sturmian Words, Lyndon Words and Trees. // Theoret. Comput. Sci. 19997. - Vol. 178. - P. 171 - 203.

97. Berstel J., Seebold P. Morphisms de Sturm. Bull. Belg. Math. Soc. Simon Stevin. 1994. - Vol. 1. -P. 175 - 189.

98. Blanchard F. ^-expansions and Symbolic Dynamics. // Theoret. Comput. Sci. 1989. - Vol. 65. - P. 131 - 141.

99. Borwein P., Erdelyi Т., Kos G. Littlewood-type Problems on 0, 1. Preprint. 29 pp.

100. Borwein P., Ingalls. The Prouhet Tarry - Escott Problem Revisited. // Ens. Math. - 1994. - Vol. 40. - P. 3 - 27.

101. Brown Т. C. Descriptions of the Charactesistic Sequence of an Irrational. // Canad. Math. Bull. 1993. - 36. - P. 15 - 21.

102. Bruck J., Goodman J.W. A Generalized Convergence Theorem for Neural Networks and its Applications in Combinatorial Optimization. // IEEE 1st. Int. Conf. Neural Networks, San Diego, С A, June 21 -24, 1987. Vol. 3. - P. 649 - 656.

103. Bruijn N. G. de. A Combinatorial Problem. // Nederl. Akad. Wetensch. Proc. 49. P. 758 764; Indagoniones Math. - 1946. - Vol. 8.-P. 461 -467.

104. Bruyere V. Automata and Codes with Bounded Deciphering Delay. In: Simon I. (ed.) Lect. Notes Comput. Sci. 1992. - Vol. 583. - P. 99-107.

105. Bruyere V., Hansel G. Bertrand Numeration Systems and Recognizability. // Theoret. Comput. Sci. 1997. - Vol. 181. - P. 17 -43.

106. Burosch G., Frankl U., Rohl S. Uber Ordnungen von Binaworten. // Rostock. Math. Kolloq. 1990. - № 39. - C. 53 - 64.

107. Cassaigne J. Unavoidable Binary Patterns. // Acta Inform. 1993. -Vol. 30.-P. 385-395.

108. Chen W. Multi-subsequence serching. // Information Processing Letters. 2000. - Vol. 74. - C. 229 - 233.

109. Chernov V.M. The "Modular Perceptron". A Linear Classes Separability in The Non-Archimedean Features Spaces. // Proc. of the10th Scandinavian Conference on Image Analysis (SCIA'97). -Lappeenranta, Finland. 1997. - Vol.2. - P. 803 - 808.

110. Chernov V.M. A Linear Classes Separability in Non-Arcimedean Spaces. // Proc. of Sixth Int. Conf. "Pattern Recognition and Information Procesing". Minsk, Belarus. - 1999. - Vol.1. - P. 35 -39.

111. Chernov V. M., Bayro-Corrochano E. Clifford Models of Image Transforms // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. 1998. - Vol. 8, № 2. - P. 272-273.

112. Chernov V.M., Shabashev A.V. Selection of p-adic Features from Texture Images // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. 1998. - Vol.8, № 2. - P. 276-279.

113. Choffrut C, Karhumaki J. Combinatorics of Words. In: Rozenberg G., Salomaa A. (eds.). Handbook of Formal Languages. 1997.-Vol. l.-P. 329- 438.

114. Chou P. A. The Capacity of the Kanerva Associative Memory is Exponential. // First IEEE Conference on Neural Networks, Denver, CO,Nov. 8- 12, 1987.-Newark,NY.- 1988.-P. 184-191.

115. Christodoulakis D. N. (ed.). Natural Language Processing NLP 2000: Proceedings of the 2nd International Conference. - Patras, Greece, June 2-4, 2000.

116. Clarke R. J., Steigrimsson E., Zeng J. The ^-extensions of Some New Mahonian Statistics. // European J. Combin. 1997.- Vol. 18.-P. 143- 154.

117. Clarke R. J., Steigrimsson E., Zeng J. New Euper Mahonian Statistics on Permutations and Words. // Adv. In Appl. Math. -1887.- 18.-P. 237-270.

118. Clarkson K.L. New Applications of Random Sampling in Computational Geometry. // Discrete Applied Geometry. 1987. — Vol. 2.-P. 195-222.

119. Clarkson K.L. Applications of Random Sampling in Computational Geometry. II. // Discrete Applied Geometry. 1989. - Vol. 4. - P. 387-421.

120. Clouse D. S., Giles C. L., Home B. G., Cottrell G. W. Time-Delay Neural Networks: Representation and Induction of Finite State Machines. // IEEE Trans. Neural Networks. 1997. - P. 1 - 15.

121. Conway J. H. The Weird and Wonderful Chemistry of Audioactive Decay. In: Cover Т., Gopinath B. (eds.). Open Problems in Communications and Computation. Springer-Verlag. 1987. c.

122. Cottrell M. Stability and Attractivity in Associative Memory Networks. // Biological Cybernetics. 1988. - Vol. 58. - P. 129 -139.

123. Coven E. M., Hedlund G. A. Sequences with Minimal Block Growth. // Math. Systems Theory. 1973. - Vol. 7. - P. 138 - 153.

124. Crama Y., Hansen P., Jaumard B. Detection of Spurious States of Neural Networks. // Neural Networks. 1991. - Vol. 2, № 1. - P. 165 -168.

125. Cucka P., Rosenfeld A. Linear Feature Compatibility for Pattern Matching Relaxation. Center for Automation Research, Univ. of Maryland, CAR-TR-530 CS-TR-2579.

126. Currie J. D. Open Problems in Pattern Avoidance. // Amer. Math. Monthly. 1993. - Vol. 100. - P. 790 - 793.

127. Danh T.-N., Daykin D. E. Sets of 0,1 Vectors with Minimal Sets of Subvectors. // Rostock Math. Colloq. 1997. - Vol. 50. - P. 47 - 52.

128. Davidson J., Hummer F., Morphology Neural Networks: An Introduction with Applications // IEEE Systems Signal Processing. -1993.-Vol. 12, №2.-P. 177-210.

129. Davidson J., Talukder A., Template Identification Using Simulated Annealing in Morphology Neural Networks // Second Annual Midwest Electro-Technology Conference, Ames, IA, IEEE Central Iowa Section, Apr. 1993. P. 64 - 67.

130. De Luca A., Varricchio S. A Finiteness Condition for Semigroups Generalizing a Theorm of Coudrain and Schiitzenberger. // Adv. in Math. 1994. - Vol. 108. - P. 91 - 103.

131. De Luca A., Varricchio S. Finiteness and Regularity in Semigroups and Formal Languages. Springer Verlag. - 1999.

132. D6sarmenien J. Consequences 6numeratives de la symetrie des fonctions de Schur. // Seminaire Lotharingien de Combinatoire. -1990.-B25a.

133. Desarmenien J., Foata D. Fonctions symetriques et series hypergeometriques basiques multivarieees. // Bull. Soc. Math. France. 1985. - Vol. 113. - P. 3 - 22.

134. Desarmenien J., Foata D. Statistiques d'ordre sur les permutations colorees. // Discrete Math. 1991. - Vol. 87. - P. 133 - 149.

135. Devolder J., Latteux M., Litovsky I., Staiger L. Codes and Infinite Words. // Acta Cybernet. 1994. - Vol. 11. - P. 241 - 256.

136. Diekert V. Matiyasevich Yu., Muscholl A. Solving Word Equations Modulo Partial Commutations. // Theoret. Comput. Sci. 1999.-Vol. 224.-P. 215-235.

137. Ehrenfeucht A., Rosenberg G. Elementary Homomorphisms and a Solution to the D0L Sequence Equivalence Problem. // Theoret. Comput. Sci. 1978. - Vol. 7. - P. 169 - 183.

138. Ehrenfeucht A., Hausler D., Rosenberg G. On Regularity of Context-Free Languages. // Theoret. Comput. Sci. 1983.- Vol. 27.-P. 311 -332.

139. Ekhad S. В., Zeilberger D. Proof of Conway's Lost Cosmological Theorem. // Electronic Res. Announc. Amer. Soc. 1997. - Vol. 3. -P. 78 - 82.

140. Engel K., Gronan H.-D. Sperner Theory in Partially Ordered Sets. BSB B.G.Teubner Verlagsgesellschaft, Leipzig. 1985. c.

141. Engelking R. General Topology. Waeszawa. 1977. 633 c.

142. Fine N. J., Wilf H. S. Uniqueness theorem for periodic functions. // Proc. Am. Math. Soc. 1965. - Vol. 16. - P. 109 - 114.

143. Floreen P. Worst-Case Convergence Times for Hopfield Memories. // IEEE Transactions on Neural Networks. 1991. - Vol. 2, № 5. - P. 533 -535.

144. Floreen P. The Convergence of Hamming Memory Networks. // IEEE Trans. Neural Networks. 1991. - Vol. 2, № 4. - P. 449 - 457.

145. Foata D. Etude algebraic de certains problemes de d'analyse combinatoire et du calcul des probabilites. // Publ. Inst. Statist. Univ. Paris. 1965.-Vol. 14.-P. 81-241.

146. Foata D., Han G. N. Calcul basique des permutations signees. I. Longeur et nombre d'inversions. // Adv. In Appl. Math. 1997.-Vol. 18.-P. 489-509.

147. Foata D., Han G. N. Transformation on Words. // J. Algorithms. -1998. 1998. - Vol. 28. - P. 172 - 191.

148. Ford L.R. Network Flow Theory. // The RAND Corp. Aug. 1956.-P. 923.

149. Freedman D. Efficient Simplicial Reconstructions of Manifolds from Their Samples. // IEEE Transactions on Pattern Analysis and machine Intelligence. 2002. - Vol. 24, № 10. - C. 1349 - 1357.

150. Frougny С. Representation of Numbers and Finite Automata. // Math. Systems Theory. 1992. - Vol. 25. - P. 37 - 60.

151. Gasper G., Rahman M. Basic Hypergeometric Series. // Encyclopedia of mathematics and its Applications. Cambridge Univ. Press, Cambridge. 1990. - Vol. 35.

152. Giles C. L., Omlin C. W. Pruning Recurrent Neural Networks for Improved Generalization Performance. // IEEE Trans. Neural Networks. 1994. - Vol. 5, No. 5. - P. 848 - 851.

153. Giles C. L., Omlin C. W., Thornber К. K. Equivalence in Knowledge Representation: Automata, Recurrent Neural Networks, and Dynamical Fuzzy Systems. // Proc. 3rd IEEE Conf. Fuzzy Systems. 1994. - Vol. 1. - P. 205 - 210.

154. Goles Ch. E., J. Olives A. The Convergence of Symmetric Threshold Automate. // Information and Control. 1981. Vol. 51.-P. 98-104.

155. Goodbeer C.H., Lipscomb J.L., Loby M. On the Computational Complexity of Finding Stable State Vectors in Connectionist Models (Hopfield Nets). // Tech. Rep. 208/88. Dept. of Computer Sciences, Univ. of Toronto. - 1988.

156. Goralcik P., Vanicek T. Binary Patterns in Binary Worda. // Inter. J. Algebra Comput. 1991. - Vol. 1. - P. 387 - 391.

157. Gupta S., Zia R. K. P. Quantum Neural Networks. // Journal of Computer and System Sciences. 2001. - Vol. 63. - P. 355 - 383.

158. Haken H. Synergetic Computers for Pattern Recognition and Associative Memory in Computational Systems, Natural and Artificial. Springer, Berlin, 1987.

159. Hand D., Mannila H., Smyth P. Principles of Data Mining. // MIT Press.-2001.

160. Hansel G. Systemes de numeration independants et sindeticite. // Theoret. Comput. Sci. 1998. - Vol. 204. - P. 119 - 130.

161. Harju Т., Karhumaki J., Petrich M. Compactnes of Equations on Completely Regular Semigroups. In: Mycielski J., Rozenberg G., Salomaa A. (eds.). Lect. Notes Comput. Sci. 1997.- Vol. 1261. -P. 268-280.

162. Haiju Т., Karhumaki J., Plandowski W. Compactnes of Systems of Equations in Semigroups. // Inter. J. Algebra Comput. 1997. - Vol. 7.-P. 457-470.

163. He Q. Knowledge Discovery Through Co-Word Analysis. // Library Trends. 1999. - Vol. 48, № 1. - p. 133 -159.

164. Higman G. Ordering by Divisibility in Abstract Algebras. // Proc. London Math. Soc. 1952. - Vol. 8. - P. 326 - 336.

165. Hopfield J.J. Neural Networks and Physical Systems with Emergent Collective Computational Abilities. // Proc. Nat. Acad. Sci. USA. -1982. Vol. 79. - P. 2554 - 2558.

166. Joo Hyoman, Haralick R. N., Shapiro L. G., Toward the AutomaticGeneration of Mathematical Morphology Procedures Using Predicate Logic // Third International Conference on Computer Vision, 1990.-P. 156-165.

167. Jorgensen P. E. Т., Pedersen S. Orthogonal Harmonic Analysis ofFractal Measures. // Electronic Research Announcements of the American Mathematical Society. 1998. - Vol. 4. - P. 35 - 42.

168. Kanerva P. Parallel Structure in Human and Computer Memory. // Neural Networks Comput., Denker, J.S., ed., New York: Am. Inst. Phys. -1986.

169. Karhumaki J. The Ehrenfeucht Conjecture: A Compactness Claim for Finitely Generated Free Monoids. // Theoret. Comput. Sci. -1984. Vol. 29. - P. 285 - 308.

170. Karhumaki J., Plandowski W. On the Size of Independent Systems of Equations in Semigroups. // Theoret. Comput. Sci. 1996. - Vol. 168.-P. 105-119.

171. Kashiwara M. Crystallization of Quantized Enveloping Algebras. // Sugaku Expositions. 1994. - Vol. 7. - P. 99 - 115.

172. Keeler J.D. Basins of Attraction in Neural Network Models. / Neural Networks for Computing: Snowbird Utah, John S. Denker (ed.). -American Institute of Physics, New York. 1986. - P. 259 - 264.

173. Kolpakov R., Kucherov G. On Maximal Repetitions in Words. In: Giobanu G, Paun G. (eds.). Lect. Notes Сотр. Sci. 1999. - P. 374 -385.

174. Kortelaineij J. On the System of Word Equations in a Free Monoid. // Journal of Automata, Languages and Combinatorics. 1998. - Vol. 3,№ l.-P. 43-57.

175. Krasikov I., Rodity Y. On a reconstruction Problem for Sequences. // Journal of Computational Theory. Seires A. 1997. - Vol. 77. - P.344.348.

176. Lascoux A., Leclerc В., Thibon J.-Y. Crystal Graphs and q-analogues of Weight Multiplicities for the Root System An. II Lett. Math. Phys. 1995. - Vol. 35. - P. 359 - 374.

177. Leclerc В., Tibon J.-Y. The Robinson Schensted Correspondence, Crystal Bases, and the Quantum Straightening at q = 0. // Electronic J. Comb. - 1996. - Vol. 3. - P. 249 - 272.

178. Leont'ev V. K., Smetanin Yu. G. Restoration of Finite Integer Sequences Given a Set of It's Subsequences. // 1st Int. Conf. on Information Technologies for Image Analysis and Pattern Recognition ITIAPR'90.- October 1990, Lviv, USSR. P. 196 -200.

179. Leont'ev V. К., Smetanin Yu. G. Problems of Information on the Set of Words. // Journal of Mathematical Sciences. Kluwer Academic/Consultants Bureau, New York, 2000.

180. Leont'ev V. K., Smetanin Yu. G. Recognition Model with Representation of Information in the Form of Long Sequences. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. 2002. - Vol. 12, No. 3. - C. 250.

181. Li Y., Smyth W. F. Computing the Cover Array in Linear Time. // Algorithmica. 2002. - Vol. 32. - C. 95 - 106.

182. Lind D., Marcus B. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, UK. 1995.

183. Lint J. H. van, Watson R. M. A Course in Combinatorics. Cambridge University Press, Cambridge, UK. 1992.

184. Lippman R.P. An Introduction to Computing with Neural Nets // IEEE ASSP Magazine. 1987. - P. 143 - 148.

185. Lipski W. On Strings Containing All Subsets as Substrings. // Discrete Mathematics. 1978. - Vol. 21. - P. 253 - 259.

186. Littelmann P. A Plactic Algebra for Semisimple Lie Algebras. // Adv. In Math. 1996. - Vol. 124. - P. 312 - 331.

187. Lothaire M. Combinatorics of Words. Encyclopedia of Mathematics and its Applications. // Addison-Wesley Publishing Co., Reading, Mass. 1983. - Vol. 17. 228 pp.

188. Lothaire M. Algebraic Combinatorics on Words. Cambridge University Press. 2002. 455 c.

189. Maier D. The Complexity of Some Problems on Subsequences and Supersequences. // J. Assoc. Comput. Mach. 1978. - Vol. 25, № 2.-P. 322-336.

190. Maier D., Storer J. A. A Note on the Complexity of the Superstring Problem. // Report No. 233.- Computer Science Laboratory, Princeton Univ., Princeton, NJ. 1977.

191. Makhoul J.,El-Zaroudi A., Schwartz R. Partitioning Capabilities of Two-Layer Neural Networks. // IEEE Transactions on Signal Processing. 1991. - Vol. 39, №. 6. - P. 1435 - 1440.

192. Mantaci S, Karhumaki J. Defect Theorems for Trees. // Fund. Inform. 1999. - Vol. 38. - P. 119 - 133.

193. Manvel В., Meyerowitz A., Schwenk A., Smith K., Stockmeyer P. Reconstruction of Sequences. Discrete Mathematics. 1991.- Vol. 94, №3.-P. 209-219.

194. Maragos P., Schafer R. Morphological filters. Part I: Their Set-Theoretic Analysis and Relations to Linear Shift-Invariant Filters // IEEE Transactions on Acoustics, Speech, and Signal Processing. -1987 . Vol. ASSP-35. - P. 1153 - 1169.

195. Maragos P. , Schafer R. Morphological filters. Part II : Their Relations to Median, Order-Statistic, and Stack Filters // IEEE Transactions on Acoustics, Speech, and Signal Processing . 1987. -Vol. ASSP-35. - P. 1170 - 1184.

196. Marathe A., Condon A. E., Corn R. M. On Combinatorial DNA Word Design. // DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2000. - Vol. 54. - P. 75 - 89.

197. Marks R.J., Atlas L.E., Oh S., Ritchy J. A. The Performance of Convex Set Projections Based Neural Networks. In: Anderson D. Z. (ed.). Neural Information Processing System, 1988. P. 534 - 543.

198. Micromorph. Implications. Centre de morphologie mathematique. Ecole nationale superieure de Mines de Paris. 1991.

199. Micromorph. Conclusions. Centre de morphologie mathematique. Ecole nationale superieure de Mines de Paris. 1991.

200. Micromorph. Applications. Centre de morphologie mathematique. Ecole nationale superieure de Mines de Paris. 1991.

201. Mignosi F., Restivo A., Salemi S. A Periodicity Theorem on Words and Applications. In: Wiedemann J., Hajek S. (eds.). Lect. Notes on Computer Science. 1995. - Vol. 969. - P. 337 - 348.

202. Mignosi F., Restivo A., Salemi S. Periodicity and the Golden Ratio. // Theoret. Comput. Sci. 1998. - Vol. 204. - P. 153 - 167.

203. Mihalache V., Salomaa A. Lindenmayer and DNA: Watson-Crick D0L Systems. // EATCS Bulletin . 1997. - 62. - P. 160 - 175.

204. Minkowski H. Volumen und Oberflache. // Math. Ann. 1903 -Vol. 57.-P. 447-495.

205. Minkowski H. Gessamelte Abbandlungen. Teubner, Leipzig -Berlin, 1911.

206. Morse M., Hedlund G. A. Unending Chess, Symbolic Dynamics and a Problem in Semigroups. // Duke Math. J. 1938. - Vol. 11. - P. 1 -7.

207. Morse M., Hedlund G. A. Symbolic Dynamics. II. Sturmian Trajectories. // Amer. J. Math. 1940. - Vol. 62. - P. 287 - 306.

208. Mortreux P., Prevost M. On Totally Monotonic Families of Sequences. // Numerische Mathematik. 1999. - Vol. 84. - P. 71 -96.

209. Palm G. On Associative Memory. // Biol. Cybernetics. 1980.-Vol. 36,№. l.-P. 19-31.

210. Paun Gh., Rozenberg G., Salomaa A. DNA Computing. New Computing Paradigms. Springer-Verlag, Berlin Heidelberg - New York. - 1998.

211. Perrin D. Equations in Words. In: Ait-Kaci H., Nivat M. (eds.). Resolution of Equations in Algebraic Structures. // Academic Press, New York. 1989. -Vol. 2. -. P. 275 - 298.

212. Pershina M. V., Chernov V.M. Fibonacci Mersenne and Fibonacci - Fermat Error-Free Convolvers // Intern. Sympos. "Optical Information Science and Technology", 27 - 30 August 1997.-Moscow. - P. 56.

213. Personnaz L. Guyon I., Dreyfus G. Collective Computational Properties of Neural Networks: New Learning Mechanisms. // Phys. Rev. A. 1986. - Vol. 34. - P. 4217 - 4228.

214. Petitcolas F. A. P. (ed.). Information Hiding 5th International Workshop. IH 2002, Noordwijkerhout, the Netherlands, October 7 -9, 2002. Revised Papers. // Lecture Notes in Computer Science. -2002.-Vol. 2578.

215. Petitcolas F. A. P., Anderson R., Kuhn M. Information Hiding a Survey. // Proc. IEEE. - 1999. - Vol. 87, No. 8. - P. 1062 - 1087.

216. Plandowski W. Satisfiability of word equations with constants is in PSPACE. Proceedings of FOCS 99. 1999. - P. 495 - 500.

217. Porat S. Stability and Looping in Connectionist Models with Asymmetric Weights. Tech. Rep. FR210. Computer Sci. Dept., Univ. of Rochester, Rochester, NY 15627. March 1987.

218. Priifer H. Neue Begruendung der algebraische Zahlentheorie. // Math. Ann. 1925. - Vol. 94, № 3 - 4. - P. 198 - 243.

219. Quine W. V. On Cores and Prime Implicants of Truth Functions. // Amer. Math. Monthley. 1959. - Vol. 66, № 9. - P. 755 - 760.

220. Raffinot M. On maximal Repeats in Strings. // Information Processing Letters. 2001. - Vol. 80. - C. 165 - 169.

221. Rajasekaran S. An Optimal Parallel Algorithm for Sorting Multisets. // Information Processing Letters. 1998. - Vol. 67. - P. 141 - 143.

222. Restivo A., Reutenauer C. Some Applications of a Theorem of Shirshov to Language Theory. // Information and Control. 1983. -Vol. 57, No. 2 - 3. - P. 205 - 213.

223. Restivo A., Reutenauer C. Rational Languages and the Burnside Problem. // Theor. Comput. Sci. 1985. - Vol. 40, no. 1. - P. 13 -30.

224. Reutenauer C. Free Lie Algebras. London Mathematical Monographs New Series. Clarendon Press, Oxford. 1993. - No. 7.

225. Ritter G. X. M. A., Wilson, J. N., and Davidson, J. N., Image Algebra: An Overview. // Сотр. Vis., Graph., Image Process. -1990. Vol. 49. - P. 297-331.

226. Ritter G.X. An Introduction to Morphological Neural Networks. // Proceedings of ICPR'96. P. 709 - 716.

227. Ritter G.X., Sussner P., Morphological Associative Memories and Perceptrons : Technical report CCVR / University of Florida. 1996.

228. Robson B. Fastfinger: A Study into the Use of Compressed Residue Pair Separation Matrices for Protein Sequence Comparison. // IBM Systems Journal. 2001. - Vol. 40, № 2. - P. 422 - 463.

229. Rosaz L. Inventories of Unavoidable Languages and the Word-Extensions Conjecture. // Theoret. Comput. Sci. 1998. - Vol. 201. -P. 151-170.

230. Rosenstiehl P. A New Proof of the Gauss Interlace Conjecture. // Adv. In Appl. Math. 1999. - Vol. 23. - P. 3 - 13.

231. Rumelhart D.F., McClelend J.L. Parallel Distributed Processing. -Cambridge, MA: MIT. 1988.

232. Salomaa A. Jewels of Formal Language Theory. Computer Science Press, Washington, DC. 1981.

233. Saupe D., Hamzaoui R., Hartenstein H., Fractal Image Compression: An Introductory Overview. In: Saupe D., Hart J. (eds.). Fractal Models for Image Synthesis, Encoding and Analysis. SIGGRAPH '96 Course Notes XX. New Orleans, 1996.

234. Seebold P. Fibonacci Morphisms and Sturmian Words. // Theoret. Comput Sci. 1991. - Vol. 88. - P. 365 - 384.

235. Seebold P. On the Conjugation of Standard Morphisms. // Theoret. Comput. Sci. 1998. - Vol. 195. - P. 91 - 109.

236. Serra J. Image Analysis and Mathematical Morphology. Vol. 1. London, Academic Press. 1982.

237. Serra J., Morphological Image Segmentation // Acta Stereol. -1995.-No. 142.-P. 99-111.

238. Shallit J., Wang M.-W. Automatic Complexity of Strings. // Journal of Automata, Languages and Combinatorics. 2001. - Vol. 6, № 4. -P. 537-554.

239. Schiitzenberger M.-P. On the Synchronizing Properties of Certain Prefix Codes. // Inform, and Control. 1964. - Vol. 7. - P. 23 - 36.

240. Simon I. Piecewise Testable Events. Automata Theory and Formal Languages. // Lecture Notes on Comput. Sci. Springer Verlag, Berlin etc. 1975. - Vol. 33. - P. 214 - 222.

241. Sitte J. Basins of Attraction and Spurious States in Neural Networks. // Abstracts of the First Annual INNS Meeting. Boston. -Pergramon Press. New York, 1988. - P. 132

242. Smetanin Yu. G. Representation of a Long Sequence with Its Component Short Sequences. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. -1991.-Vol. 1, № 2. P. 195-199.

243. Smetanin Yu. G. A Monte-Carlo Algorithm for Matching the Images Represented by Sets of Fragmentary Features. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. // 1993. Vol.3, №. 3. - P. 285 - 288.

244. Smetanin Yu. G. Random Sampling in the Estimation of the Number of Attraction Basins in Neural Networks. // Pattern Recognition and1.age Analysis: Advances in Mathematical Theory and Applications. 1994. - Vol.4, №. 1. - P. 74 - 77.

245. Smetanin Yu. G. A Las Vegas Method of Region of Attraction Enlargement in Neural Networks. // The International Society for Optical Engineering, Bellingham. SPIE. 1994. - Vol. 2363. - P. 77 -84, 104- 108.

246. Smetanin Yu. Neural Networks as Systems for Pattern Recognition: A Review. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. 1995. - Vol.5, №. 2. - P. 254-293.

247. Smetanin Yu. A Neural Network for Determining Shortest Paths in a Graph. // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. 1995. - Vol. 5, № 3. - P. 376-378.

248. Smetanin Yu. G. Neural Networks as Systems for Pattern Recognition. // Journal of Mathematical Science. 1998.- Vol. 89, №.4.-P. 1406- 1457.

249. Thue A. Uber mendliche Zeichenreichen. // Norske Vid. Selsk. Skr. I Math. Nat. Kl. 1906. - Vol. 7. - P. 1 - 22.

250. Thue A. Uber die gegenseitige Loge gleicher Teile gewisser Zeichenreichen. // Norske Vid. Selsk. Skr. I Math. Nat. Kl. Chris. -1912.-Vol. l.-P. 1-67.

251. Tino P. Spatial Representation of Symbolic Sequences Through Iterative Function Systems. // IEEE Trans. Syst., Man, and Cybernetics A: Systems and Humans. 1999. - Vol. 4. - P. 386 -392.

252. Tomescu I. On Words Containing all Short Subwords. // Theoretical Computer Science. 1998. - Vol. 197. - P. 235 - 240.

253. Tseng Y.-C., Chen Y.-Y., Pan H.-K. A Secure data Hinding Scheme for Binary Images // IEEE Transactions on Communications. -2002. Vol. 50, No. 8. - C. 1227 - 1231.

254. Van der Bout, D.E., Miller Т.К., Graph Partitioning Using Annealed Neural Networks. // IEEE Trans. Neural Networks. 1990.- Vol. l.-P. 192-203.

255. Vandeth D. Sturmian Words and Words with a Critical Exponent. // Theoret. Comput. Sci. 2000. - Vol. 242. - P. 283 - 300.

256. Venkatesh S.S. Computation and Learning in the Context of Neural Network Capacity. / Neural Networks for Perception, Wechsler H.,ed. Vol. 2. // Academic Press, Inc. Harcourt Race Jovanovich Publishers. 1992.-P. 173-210.

257. Wang J. T. L., Ma Q., Shasha D., Wu С. H. New Techniques for Extracting Features from Protein Sequences. // IBM Systems Journal. 2001. - Vol. 40, № 2. - P. 426 - 441.

258. Wieselthier J. E., Barnhart С. M., Ephremides A. A Neural Network Approach to Routing without Interference in Multihop Radio Networks. // IEEE Trans, on Communications. 1994. - Vol. 42, № l.-P. 166- 177.

259. Wilcox A, Hripcsak G. Knowledge Discovery and Data Mining to Assist Natural Language Understanding. // Proceedings of the AMIA Annual Fall Symposium. 1998 - P. 835 - 839.

260. Xie X., Seung H. S. Equivalence of Backpropagation and Contrastive Hebbian Learning in Layered Network. // Neural Computation. 2003. - 15. C. 441 - 454.

261. Ying M. A Formal Model of Computing with Words. // IEEE Transactions on Fuzzy Systems. 2002. - Vol. 10, No. 5. - P. 640 -652.

262. Yu P., Anastassopoulos V., Venetsanopoulos A.N. Pattern Recognition Based on Morphological Shape Analysis and Neural Networks // Mathematics and Computers in Simulation. 1996. - № 40.-P. 577-596.