Мельников Сергей Юрьевич Методы распознавания и идентификации конечных автоматов по статистическим характеристикам выходных и входных последовательностей

Краткое описание

Мельников Сергей Юрьевич Методы распознавания и идентификации конечных автоматов по статистическим характеристикам выходных и входных последовательностей

ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ

доктор наук Мельников Сергей Юрьевич

ВВЕДЕНИЕ

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

Введение

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

1.1.1 Вероятностная функция автомата

1.1.2 Задача распознавания функции выходов. Статистическая эквивалентность

1.1.3 Границы для числа классов эквивалентности

1.1.4 Определение класса эквивалентности функции выходов по статистике встречаемости выделенного слова

§ 1.2 Задача распознавания булевой функции выходов проходного регистра сдвига с бернуллиевским входом

1.2.1 Вероятностная функция регистра сдвига

1.2.2 Структура отношения статистической эквивалентности

1.2.3 Свойства множества «особенных распределений»

1.2.4 Определение класса статистической эквивалентности функции выходов по значковой статистике

§ 1.3 Задача распознавания булевой функции выходов двоичного проходного регистра сдвига с марковским входом

1.3.1 Автоматы, перерабатывающие последовательности зависимых случайных величин

1.3.2 Постановка задачи

1.3.3 Вычисление вероятности Р.^ . Геометрическая трактовка

1.3.4 Отношение статистической эквивалентности при марковской зависимости на входе и его свойства

1.3.5 Определение класса статистической эквивалентности функции выходов по значению вероятностной функции при марковской входной зависимости

1.3.6 Определение класса статистической эквивалентности неизвестной функции выходов по значковой статистике при марковской входной зависимости

1.3.7 Сравнение «марковского» и «бернуллиевского» случаев

§ 1.4 Задача распознавания функции выходов для обобщений регистра сдвига

1.4.1 Двоичные обобщенные в смысле 1шаве и ЙоЬ регистры сдвига и их вероятностная функция

1.4.2 Двоичные регистры сдвига с внутренним суммированием и их вероятностная функция

Выводы по главе

ГЛАВА 2. ИСПОЛЬЗОВАНИЕ СПЕКТРОВ ГРАФОВ В ЗАДАЧЕ РАСПОЗНАВАНИЯ НЕИЗВЕСТНОЙ ФУНКЦИИ ВЫХОДОВ АВТОМАТОВ И ДРУГИХ ТЕОРЕТИКО-

АВТОМАТНЫХ ЗАДАЧАХ

Введение

§ 2.1 Использование спектров графов автоматов в задаче распознавания функции выходов по вероятностям биграмм в выходной последовательности

2.1.1 Представление вероятности биграммы 1( в виде квадратичной формы

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

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

2.2.1 Характеристические многочлены неориентированного графа де Брейна и его степеней

2.2.2 Верхняя граница числа независимости графа де Брейна и его степеней

2.2.3 Регистры сдвига со случайным неравномерным движением

§ 2.3 Редуцированные графы де Брейна и обобщенные регистры сдвига

2.3.1 Спектры к-циркулянтных матриц

2.3.2 Об обобщениях графов де Брейна

2.3.3 Свойства редуцированного графа де Брейна

2.3.4 Количество остовных деревьев и эйлеровых циклов

2.3.5 Количество полноцикловых регистров сдвига (формула Гуда - де Брейна)

2.3.6 О планарности графов 0(п,ш)

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

Выводы по главе

ГЛАВА 3. МНОГОГРАННИКИ, ХАРАКТЕРИЗУЮЩИЕ СТАТИСТИЧЕСКИЕ СВОЙСТВА КОНЕЧНЫХ АВТОМАТОВ. ИХ СВОЙСТВА И МЕТОДЫ ПОСТРОЕНИЯ. ПРОВЕРКА ГИПОТЕЗЫ О НЕИЗВЕСТНОМ АВТОМАТЕ ПО ОТРЕЗКАМ ВХОДНОЙ И ВЫХОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

Введение

§ 3.1 Определение многогранника автомата

§ 3.2 Строение многогранника автомата

§ 3.3 Обработка автоматами конечных последовательностей

§ 3.4 Метод идентификации автоматов с использованием многогранников

§ 3.5 Чезаровские последовательности и чезарово-наследственные автоматы

§ 3.6 Чезарово-наследственность регистров сдвига

3.6.1 Чезарово-наследственность обобщенных по Imase и Ко И регистров сдвига

3.6.2. Чезарово-наследственность регистров сдвига с внутренним суммированием .. 112 3.6.3 Замечание о статистической стабилизации относительных частот в р-адической

области

§ 3.7 Автоматы, сохраняющие значковые статистические свойства входной последовательности

3.7.1 Постановка задачи для регистра сдвига. Пример

3.7.2 Свойства функций из класса Мп

3.7.3 Критерий принадлежности функции классу Мп

3.7.4 Оценки мощности класса Мп

3.7.5 О сохранении значковых статистических свойств входной последовательности обобщениями регистров сдвига

Выводы по главе

ГЛАВА 4. МНОГОУГОЛЬНИКИ, ХАРАКТЕРИЗУЮЩИЕ СТАТИСТИЧЕСКИЕ

СВОЙСТВА НЕКОТОРЫХ КЛАССОВ КОНЕЧНЫХ АВТОМАТОВ

Введение

§ 4.1 Многоугольники, характеризующие значковые статистические свойства

проходного регистра сдвига с булевой функцией выходов

4.1.1. Определение многоугольника булевой функции

4.1.2 Циклы графа де Брейна и строение многоугольников булевых функций

4.1.3 Свойства многоугольников булевых функций

4.1.4 Многоугольники некоторых линейных функций и функций, инвариантных относительно циклического сдвига аргументов

4.1.5 Классификация функций выходов по многоугольникам для малого числа переменных. Случай регистра сдвига

4.1.6 Примеры. Обработка регистрами А последовательностей различной длины

§ 4.2 Многоугольники, характеризующие значковые статистические свойства регистра сдвига с внутренним суммированием с булевой функцией выходов

4.2.1 Определение многоугольника автомата А]

4.2.2 Свойства многоугольника автомата А]

4.2.3 Оценка количества регистров с максимальными многоугольниками

§ 4.3 Многоугольники, характеризующие совместные значковые и биграммные

статистические свойства выходной последовательности проходного регистра сдвига с булевой функцией выходов

4.3.1 Определение и построение многоугольников

4.3.2 Максимальные по включению многоугольники

4.3.3 Свойства многоугольников

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

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

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

4.4.2 Оценка количества функций с максимальными многоугольниками

§ 4.5 Анализ эффективности метода многогранников автоматов на основе

статистической модели распределения множества многогранников

4.5.1 Описание подхода

4.5.2 Случай автоматов из семейства регистров сдвига

4.5.3 Результаты вычислительного эксперимента

4.5.4 Анализ результатов вычислительного эксперимента

4.5.5 Параметры метода многогранников, влияющие на его эффективность

Выводы по главе

ГЛАВА 5. СОПОСТАВЛЕНИЕ МЕТОДОВ ИДЕНТИФИКАЦИИ КОНЕЧНЫХ АВТО

МАТОВ И МЕТОДОВ ИДЕНТИФИКАЦИИ ЯЗЫКА СООБЩЕНИЙ

Введение

§ 5.1 Задача идентификации языка сообщения и ее разновидности. Особенности идентификации языка текстовых и речевых сообщений, печатных и рукописных текстов

5.1.1 Задача идентификации языка сообщения и ее разновидности

5.1.2 Актуальность задачи идентификации языков

§ 5.2 Подходы к задаче идентификации языка. Связь с задачей идентификации автоматов

5.2.1 Постановка задачи. Байесовский подход

5.2.2 Подходы к задаче идентификации языка текста

5.2.3 Подходы к задаче идентификации языка речевого сообщения

5.2.4 Подходы к идентификации языка для графических изображений. Печатный и рукописный текст

§ 5.3 Генераторы искусственных текстов (ГИТ) как конечные вероятностные автоматы

5.3.1 Генератор искусственного текста на основе цепей Маркова (ГИТ ЦМ)

5.3.2 Системы Nitrogen и Halogen

5.3.3 Логическая и функциональная структура ГИТ

5.3.4 Генераторы параллельных текстов на нескольких языках

5.3.5 Об оценках качества искусственно сгенерированных текстов

§ 5.4 Идентификация языка текста со случайными искажениями. Результаты

экспериментов. Теоретико-информационный подход

5.4.1 Первый тип искажений: пропуск, вставка, замена (вероятности фиксированы)

5.4.2 Второй тип искажений: замена (вероятности нефиксированы)

5.4.3 Теоретико-информационный подход. Оценка пропускной способности канала, моделирующего искажения

Выводы по главе

ПЕРСПЕКТИВНЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЯ

Приложение А ДОКУМЕНТЫ, ПОДТВЕРЖДАЮЩИЕ ВНЕДРЕНИЕ ОСНОВНЫХ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ