Реконструкция по частичным представлениям в комбинаторике слов тема диссертации и автореферата по ВАК РФ 05.13.17, доктор физико-математических наук Сметанин, Юрий Геннадиевич

• Сметанин, Юрий Геннадиевич
• доктор физико-математических наук
• 2003

Оглавление диссертации доктор физико-математических наук Сметанин, Юрий Геннадиевич

Введение

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

Глава 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-множеств.

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

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

Список литературы диссертационного исследования доктор физико-математических наук Сметанин, Юрий Геннадиевич, 2003 год

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.