Методы распознавания и идентификации конечных автоматов по статистическим характеристикам выходных и входных последовательностей тема диссертации и автореферата по ВАК РФ 05.13.17, доктор наук Мельников Сергей Юрьевич
Мельников Сергей Юрьевич
доктор наук
2021
- Специальность ВАК РФ05.13.17
- Количество страниц 265
Оглавление диссертации доктор наук Мельников Сергей Юрьевич
ВВЕДЕНИЕ
ГЛАВА 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 Теоретико-информационный подход. Оценка пропускной способности канала, моделирующего искажения
Выводы по главе
ПЕРСПЕКТИВНЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЯ
Приложение А ДОКУМЕНТЫ, ПОДТВЕРЖДАЮЩИЕ ВНЕДРЕНИЕ ОСНОВНЫХ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ
ВВЕДЕНИЕ
Актуальность темы исследования. Интенсивно развивающиеся сети связи являются неотъемлемой частью жизни информационного общества. Современные сети используют огромное число разновидностей оборудования приема, передачи и обработки информации. При разработке и анализе такого оборудования необходимо решение целого ряда идентификационных задач. Общепринятой моделью дискретных устройств являются конечные автоматы. Диссертационная работа посвящена проблеме идентификации конечных автоматов, которые обрабатывают случайные или псевдослучайные данные, по наблюдениям над выходной и входной последовательностями.
Проблема идентификации конечных автоматов относится к классической задаче математической кибернетики о «черном ящике». Она включает в себя вопросы распознавания, восстановления, контроля и диагностики автоматов.
В диссертации под распознаванием автоматов понимается указание таких автоматов из заданного класса, которые соответствуют наблюдаемым свойствам выходной и входной последовательностей, под идентификацией автомата понимается проверка гипотезы о том, что последовательности, свойства которых наблюдаются, были получены с помощью эталонного автомата.
Перечислим области, в которых исследуемая проблема является актуальной.
В области технической диагностики дискретных устройств важное место занимает вероятностное тестирование. На вход тестируемого и исправного устройств подаются случайные данные с заданными вероятностными характеристиками, а обнаружение неисправности достигается путем сравнения статистических характеристик выходных последовательностей. Решение задачи распознавания автоматов позволит указать конкретный тип неисправности устройства.
В ряде криптоаналитических приложений необходимо проверять гипотезы о том, что анализируемый узел реализует тот или иной алгоритм шифрования, ключ которого неизвестен. Задачи идентификации и распознавания возникают, если к самому узлу доступа у исследователя нет, а для анализа может быть доступна полная или частичная информация о выходной и, в ряде случаев, о входной последовательностях.
При разработке генераторов случайных последовательностей (ГСП) необходимо обеспечить неотличимость получаемой последовательности от случайной. Ситуация, при которой по выходной последовательности возможна идентификация генератора или его отдельных узлов, свидетельствует о плохом качестве ГСП.
При поиске скрытых каналов в информационных системах, когда требуется узнать, не произведено ли несанкционированное изменение алгоритмов их функционирования, необходима идентификация систем и их отдельных узлов по статистическим свойствам входных и выходных потоков данных. Эта задача соответствует п.2.1.3 «Основных направлений научных исследований в области обеспечения информационной безопасности Российской Федерации», утвержденным в 2017 г.
Разработка новых методов идентификации автоматов актуальна также для задач обработки материалов на естественных языках. Аппарат детерминированных и вероятностных конечных автоматов в последние годы активно используется для моделирования естественных языков, генерации искусственных текстов, автоматического перевода, коррекции ошибок в текстах, построения моделей интерактивного общения «человек-компьютер». Потребность в эффективно работающих системах, решающих идентификационные задачи по наблюдениям над фрагментами текста или речевого сигнала, в последние годы сильно выросла и продолжает расти, что связано с глобализацией систем и сетей связи и развитием технологий контроля трафика. Одной из практически важных задач здесь является задача распознавания языка текстовых и речевых сообщений. Актуальность теоретико-автоматного похода к задаче идентификации языка возрастает с развитием многоязычных генераторов искусственных текстов, которые моделируются конечными автоматами.
При идентификации автомата важно определить, с какой точностью имеющиеся данные о выходных и входных последовательностях позволяют идентифицировать автомат. При диагностировании устройств это позволит ограничить круг возможных неисправностей, в криптоаналитических приложениях это необходимо для анализа стойкости криптографических преобразований.
Говоря о точности идентификации автомата в содержательном смысле, необходимо ввести ограничения на класс рассматриваемых автоматов. Такие ограничения могут касаться, например, числа состояний автомата, множеств алфавитов, вида функции переходов или выходов. Частным случаем применения таких ограничений является класс автоматов с фиксированными алфавитами, множеством состояний и функцией переходов. Важнейшими классами автоматов, часто используемыми в ГСП, являются регистры сдвига и их модификации. Функции выходов таких автоматов предназначены для усложнения последовательности состояний. В этом случае автомат может быть идентифицирован с точностью до некоторого набора функций выходов, что приводит к той или иной классификации множества дискретных функций.
Для решения перечисленных задач используется два подхода: детерминированный и вероятностный. Детерминированный подход связан с поочередной установкой исследуемых
устройств и систем во все возможные начальные состояния и последующей проверкой свойств генерируемых последовательностей. Вероятностный подход использует вероятностное моделирование входных последовательностей и расчет вероятностных характеристик выходных последовательностей.
С ростом сложности анализируемых устройств и систем оба подхода сталкиваются с серьезными трудностями. Детерминированный подход подразумевает перебор состояний автомата и ограничен доступными вычислительными ресурсами. Так, в криптоаналитических приложениях в качестве ключей шифрования, как правило, используются начальные состояния, число которых выбирается разработчиками из соображений невозможности перебора на современных и перспективных средствах вычислительной техники. При вероятностном подходе, как правило, используются базовые модели зависимости между членами анализируемых последовательностей - независимые испытания и цепи Маркова. В ряде случаев они оказываются слишком грубыми для описания свойств реальных последовательностей.
Степень разработанности темы. На сегодняшний день проблеме идентификации конечных автоматов посвящено значительное количество работ, среди которых можно выделить два направления в зависимости от использования модели случайности входной последовательности.
Направление, не предполагающее случайности входной последовательности, является исторически первым и принадлежит интенсивно развивающейся теории экспериментов с автоматами. В рамках этого направления предполагается, что известны отрезки входной и выходной последовательностей анализируемого автомата, и в ряде случаев возможно управление входной последовательностью. Теоретические и прикладные основы исследований в этом направлении базируются в основном на результатах в области перечислительных методов дискретной математики, теории графов, теории дискретных функций, теории конечных автоматов. В числе отечественных исследователей следует назвать Богомолова А.М., Грунского И.С., Кудрявцева В.Б., Никонова В.Г., Погорелова Б.А., Пудовкину М.А, Сачкова В.Н., Сумарокова С.Н., Трахтенброта Б.А. и др., а наиболее значимыми зарубежными авторами являются Cerny J., Gill A., Ginsburg S., Moore E.F., Rabin M.O. и др.
Второе направление, связанное с заданием той или иной вероятностной меры на пространстве входных последовательностей, развивается в исследованиях автоматов со случайным входом и теории вероятностных автоматов. В рамках этого направления, как правило, предполагается, что вероятностная мера на пространстве входных последовательностей задана и известны значения вероятностей набора мультиграмм в выходной последовательности анализируемого автомата. В исследованиях в этом направлении возникают разновидности отношений статистической эквивалентности между автоматами.
В частности, в предположении независимости членов входной последовательности статистическая эквивалентность может рассматриваться как при произвольном полиномиальном распределении на входном алфавите, так и при заданном, обычно равновероятном. Кроме этого, в ряде работ ограничивается размер мультиграмм.
Теоретические и прикладные основы исследований в этом направлении базируются в основном на результатах в области вероятностных методов дискретной математики, теории кодирования, теории вероятностей, теории случайных процессов. В числе отечественных исследователей следует назвать Балакина Г.В., Барашко А.С., Башарина Г.П., Бухараева Р.Г., Грушо А.А., Крука Е.А., Орлова Ю.Н., Рожкова М.И., Самуйлова К.Е., Севастьянова Б.А., Тимонину Е.Е. и др., а наиболее значимыми зарубежными авторами являются Hadjicostis C.N., Marsaglia G., Paz A., Rabin M.O., Vadhan S.P. и др.
Методы идентификации автоматов, разрабатываемые в обоих указанных направлениях, обладают определенными ограничениями. Они могут требовать подачи на вход анализируемого автомата специальным образом подобранных детерминированных или случайных последовательностей с заданной вероятностной мерой и/или установки его в известное начальное состояние, что в ряде приложений невозможно.
Таким образом, необходимы методы идентификации конечных автоматов, которые:
- основаны на наблюдениях над входными и выходными последовательностями,
- не используют информацию о начальном состоянии анализируемого автомата,
- не требуют подачи на вход автомата специально подобранных последовательностей.
Настоящая диссертационная работа посвящена созданию именно таких методов, что и
Рекомендованный список диссертаций по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм2011 год, доктор технических наук Рожков, Михаил Иванович
Распознавание конечных детерминированных автоматов методом зацикливания2004 год, кандидат физико-математических наук Кунявская, Анна Наумовна
Гистограммная функция автомата и ее приложения2015 год, кандидат наук Пархоменко, Денис Владимирович
Об автоматных функциях с магазинной памятью2017 год, кандидат наук Иванов, Илья Евгеньевич
Идентификация и классификация автоматных марковских моделей методами многопараметрического анализа2018 год, кандидат наук Нурутдинова, Алсу Рафаиловна
Введение диссертации (часть автореферата) на тему «Методы распознавания и идентификации конечных автоматов по статистическим характеристикам выходных и входных последовательностей»
обеспечивает ее актуальность.
Цель и задачи исследования. Диссертация посвящена решению фундаментальной научной проблемы - созданию теоретических основ, моделей и методов распознавания и идентификации конечных автоматов по входным и выходным данным, без использования информации о начальном состоянии автомата.
Для достижения цели в диссертационной работе решены следующие основные задачи.
1. Разработка методов распознавания автомата по отрезку выходной последовательности, не требующих установки автомата в фиксированное состояние, с использованием вероятностных моделей входной последовательности, и получение оценок точности распознавания.
2. Исследование совместных статистических свойств входной и выходной последовательностей автомата и построение способа их геометрического описания.
3. Разработка методов идентификации автомата по отрезкам входной и выходной последовательностей, не требующих установки автомата в фиксированное состояние, без
использования вероятностных моделей входной последовательности, и получение оценок неоднозначности идентификации.
4. Создание новых принципов классификации дискретных функций, основанных на анализе статистических свойств автоматов с данными функциями выходов.
5. Исследование точности методов распознавания языка дискретных последовательностей естественного происхождения, таких как речь, текст, искаженный текст, в условиях случайных искажений.
6. Экспериментальное подтверждение разработанных методов идентификации.
Предмет исследования - методы идентификации и распознавания конечных автоматов.
Методы исследования. Для решения поставленных задач в диссертационной работе
использовались методы теории автоматов, теории графов, комбинаторного анализа, теории вероятностей и математической статистики, теории дискретных функций. Вероятностные распределения на состояниях автоматов исследовались с помощью элементов теории случайных процессов. Анализ распределений биграмм в выходных последовательностях автоматов проводился с привлечением положений теории спектров графов. При описании свойств автоматных преобразований бесконечных последовательностей применялись методы функционального анализа. Теоретические результаты по идентификации автоматов подтверждались компьютерными экспериментами. Для оценки точности распознавания языков искаженных текстов использовался аппарат теории информации.
Научная новизна
1. Предложен метод распознавания функции выходов автомата со случайным полиномиальным входом с точностью до класса статистической эквивалентности. Отличие метода от известных состоит в использовании целочисленной минимизации модуля линейной формы для определения класса эквивалентности.
2. Предложен метод распознавания функции выходов вероятностного автомата по значениям вероятностей биграмм в его выходной последовательности. Метод отличается сведением задачи распознавания к решению системы квадратичных уравнений, которая в случае автоматов с симметрической матрицей переходов допускает линеаризацию.
3. Предложен метод вычисления спектров обобщенных графов де Брейна, неориентированных степеней графов де Брейна и рангов квадратичных форм, соответствующих вероятностям выходных биграмм регистра сдвига со случайным входом. Метод отличается от известных использованием преобразования унитарного подобия матрицы смежности графа автомата.
4. Разработан метод идентификации автоматов с использованием многогранников, описывающих геометрические области возможных совместных статистических характеристик входной и выходной последовательностей. Метод идентификации с использованием многогранников существенно обобщает известный метод идентификации автоматов по запретам в выходной последовательности.
5. Разработаны способы решения задачи эффективного построения многогранников автоматов для нескольких классов автоматов, основанные на известных комбинаторных алгоритмах.
6. Предложен новый принцип классификации булевых функций, отличающийся от известных использованием многоугольников автоматов, в которых эти функции являются выходными. Выделен класс булевых функций, которые в схеме регистра сдвига обладают уникальными свойствами, гарантирующими наследование значковых статистических свойств входной последовательности.
7. Предложена модель случайных искажений для оценивания точности методов идентификации языка искаженного текста и проведен ее теоретико-информационный анализ.
Положения, выносимые на защиту
1. Анализ структуры отношения статистической эквивалентности, которое возникает при равенстве пределов относительных частот встречаемости фиксированного слова, позволяющий строить методы распознавания функций выходов автоматов со случайным входом по статистическим свойствам выходной последовательности.
2. Анализ спектральных свойств неориентированных степеней графа переходов автомата, позволяющий разрабатывать методы распознавания функции выходов конечного вероятностного автомата по значениям вероятностей биграмм в его выходной последовательности.
3. Способы получения спектральных характеристик обобщенных графов де Брейна и неориентированных степеней ^-ичных графов де Брейна, позволяющие вычислять значения ряда их теоретико-графовых констант.
4. Описание совместных статистических свойств входной и выходной последовательностей с помощью многогранников, позволяющее разрабатывать методы идентификации автоматов по отрезкам выходных и, возможно, входных последовательностей без перебора начальных состояний.
5. Методы, позволяющие исследовать свойство устойчивости относительных частот встречаемости произвольных слов в растущих начальных отрезках выходной последовательности регистров сдвига и близких к ним автоматов.
6. Новый принцип классификации дискретных функций, основанный на использовании многогранников автоматов. Определены автоматы, сохраняющие значковые статистические характеристики двоичной входной последовательности. Разработанные методы позволяют исследовать наличие такого свойства у регистров сдвига.
7. Экспериментальные оценки точности мультиграммных методов идентификации языка текста со случайными искажениями в зависимости от уровня искажений и их теоретико-информационный анализ.
Теоретическая и практическая значимость. В диссертационной работе сделан вклад в теоретические основы методов идентификации автоматов со случайным и псевдослучайным входом. Предложенные в работе методы могут быть применены для разработки и анализа генераторов случайных чисел, для разработки методов поиска скрытых каналов в информационных системах, для решения задач технической диагностики дискретных устройств, для построения систем автоматической обработки текстовых материалов. Ряд результатов диссертационной работы использован при выполнении НИОКР, проводимых ООО «Лингвистические и информационные технологии» в интересах государственных заказчиков, где автор являлся научным руководителем и исполнителем, в том числе по гранту РФФИ и проекту «Семантика» ФПИ. Получено свидетельство о государственной регистрации разработанного программного средства.
Достоверность полученных результатов подтверждается математически корректными выводами и доказательствами теорем и других утверждений, корректностью разработанных математических моделей, использованием известных положений фундаментальных методов, соответствием полученных теоретических результатов данным проведенных вычислительных экспериментов и опубликованным результатам исследований других авторов.
Соответствие паспорту специальности. Диссертационное исследование выполнено в соответствии с паспортом специальности 05.13.17 «Теоретические основы информатики» и включает оригинальные результаты в области исследования процессов накопления и обработки информации, исследования методов преобразования информации в данные, создания и исследования информационных моделей, моделей данных, а также исследования принципов создания и функционирования аппаратных и программных средств автоматизации указанных процессов. Диссертационное исследование соответствует следующим разделам паспорта специальности 05.13.17 «Теоретические основы информатики»:
5. Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях, разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений.
10. Разработка основ математической теории языков и грамматик, теории конечных автоматов.
11. Разработка методов обеспечения высоконадежной обработки информации и обеспечения помехоустойчивости информационных коммуникаций для целей передачи, хранения и защиты информации; разработка основ теории надежности и безопасности использования информационных технологий.
Апробация работы. Научные положения и результаты диссертационной работы докладывались и получили одобрение на следующих семинарах и конференциях: Всероссийских симпозиумах по прикладной и промышленной математике (2004, 2006, 2007, 2009-2020), I, II и III Международных конференциях «Системный анализ и информационные технологии» (2005-2009), Международных конференциях «Информационные технологии и искусственный интеллект» (Кацивели, 2006, Дивноморское, 2007), XII и XIV Международных конференциях Speech and Computer SPECOM 2007 (Москва, 2007), SPECOM 2011 (Казань, 2011), Х Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2008), всероссийских научно-технических конференциях «Суперкомпьютерные технологии СКТ-2016, СКТ-2018, СКТ-2020» (Дивноморское, 2016, 2018, 2020), всероссийских мультиконференциях по проблемам управления «МКПУ-2015», «МКПУ-2017», «МКПУ-2019» (Дивноморское, 2015, 2017, 2019), II Балтийском международном симпозиуме по прикладной и промышленной математике и XXXIV Международном семинаре по проблемам устойчивости стохастических систем (Светлогорск, 2016 г.), научно-практических конференциях «Комплексная защита информации» (Смоленск, 2016, Минск, 2021), на Международных конференциях «Распределенные компьютерные и телекоммуникационные сети: теория и приложения» DCCN-2018, DCCN-2020 (Москва, 2018, 2020), на III Международной конференции по инженерной и прикладной лингвистике «Пиотровские чтения-2019» (Санкт-Петербург, 2019), на X конференции с международным участием «Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем» ITTMM-2020 (Москва, 2020), на XX Международной конференции по проводным и беспроводным сетям и системам следующего поколения NEW2AN/ruSMART-2020 (Санкт-Петербург, 2020), IV Международной конференции по сетям будущего и распределенным вычислительным системам ICFNDs-2020 (Санкт-Петербург, 2020), на семинаре института экономики, математики и информационных технологий РАНХиГС (Москва, 2018), на межвузовских семинарах «Современные телекоммуникации и математическая теория телетрафика» (учредители: РУДН, МТУСИ, ИППИ РАН, ТГУ) (Москва, 2018-2021).
Публикация результатов работы. Основные результаты диссертации изложены в 48 опубликованных работах, в том числе в 1 монографии; в 17 статьях, опубликованных в журналах, включенных в Перечень РУДН/ВАК, в 11 статьях, опубликованных в источниках, индексируемых Web of Science и Scopus.
Личный вклад автора. Результаты, вынесенные на защиту, получены автором самостоятельно. Результаты по обобщенным графам де Брейна получены в соавторстве с Максимовским А.Ю., автору принадлежит метод доказательства. Решения по распознаванию языка искаженных текстов разработаны в соавторстве с Кулаем А.Ю., автору принадлежат постановка задач и методика исследований. Направления исследований диссертационной работы, формулировки проблем и постановки задач обсуждались с научным консультантом проф. Самуйловым К.Е., что отражено в совместных публикациях, в которых основные результаты и их доказательства принадлежат диссертанту.
ГЛАВА 1. ЗАДАЧА РАСПОЗНАВАНИЯ ФУНКЦИИ ВЫХОДОВ КОНЕЧНОГО АВТОМАТА СО СЛУЧАЙНЫМ ВХОДОМ ПО НАБЛЮДЕНИЯМ НАД ВЫХОДНОЙ
ПОСЛЕДОВАТЕЛЬНОСТЬЮ
Введение
В главе рассматриваются конечные автоматы со случайным входом, функция выходов которых неизвестна и подлежит распознаванию по наблюдениям над выходной последовательностью.
Глава состоит из четырех параграфов.
В §1 рассматривается случай произвольного сильносвязного автомата Мура. Предполагается, что входная последовательность является последовательностью неависимых одинаково распределенных случайных величин с известным полиномиальным распределением на входном алфавите автомата. Изучаются возможности распознавания функции выходов автомата по точному значению вероятности и по статистике встречаемости фиксированного слова в выходном алфавите в выходной последовательности автомата. В §2 и 3 изучаются задачи распознавания неизвестной булевой функции выходов двоичного проходного регистра сдвига (для бернуллиевской и марковской моделей входной последовательности) по значковым характеристикам выходной последовательности. В §4 в рамках той же задачи рассматриваются два класса автоматов, в определенном смысле близких к сдвиговым регистрам, с бернуллиевской последовательностью на входе.
С такими постановками связан ряд теоретических и прикладных задач, рассматриваемых в литературе. Перечислим некоторые их них. Задача выбора минимального набора мультиграмм в выходной последовательности, вероятности которых характеризуют автомат, приводит к задаче анализа алгебраических свойств семейства вероятностных распределений таких мультиграмм, как функции от вероятностного распределения на входе ([160], [161], [65], [203]). В [139] содержится обзор работ по близкой задаче: известны вероятности мультиграмм некоторого стационарного случайного процесса с дискретным числом состояний, и требуется определить, является ли этот процесс функцией на цепи Маркова. В работе [301] для проходного регистра сдвига со случайным входом получены оценка размера выходных s-грамм, набор вероятностей которых задает класс эквивалентности такого автомата, и оценки количества классов эквивалентности.
Любой вероятностный автомат представим ([180], [115]) в виде последовательного соединения «источника вероятности», порождающего случайным и независимым образом символы некоторого алфавита с заданными вероятностями, и детерминированного конечного
автомата. В ряде работ (см. обзор [212]) рассматривалась задача о синтезе такого «источника вероятности», в частности, выработки критериев, позволяющих определить, порождается ли искомое значение комбинацией бернуллиевских случайных величин с вероятностями из заданного множества. В [337]) рассматривается задача аппроксимации распределений бернуллиевских с. в. (случайных величин) путем применения булевых функций из замкнутого класса к независимым с. в. с заданным распределением.
Поиск новых методов вычислений приводит к задаче анализа класса функций, описывающих вероятности мультиграмм в выходной последовательности, как функций действительных переменных ([303]).
Большое число работ посвящено задаче тестирования дискретных устройств путем подачи на них случайных последовательностей (тестов) и анализа статистик на выходах ([193], [54] и др.). Задача определения неисправности устройства в такой постановке является задачей распознавания автоматов ([231]). Это направление называют случайным или псевдослучайным тестированием (random testing, pseudorandom testing). Как отмечается в [313], актуальность этого направления связана с высоким объемом вычислений, необходимых для построения детерминированных тестов для сложных дискретных устройств. Особое место занимают методы вероятностного компактного тестирования, при которых неисправности обнаруживаются путем сравнения некоторой статистической характеристики тестируемого и исправного устройств. Такой характеристикой может служить частота появления в выходной последовательности фиксированной подпоследовательности выходных сигналов. Возможность изменять анализируемую подпоследовательность и параметры генератора случайных сигналов на входе устройства является мощным средством в руках исследователя. В [55] описаны ситуации, когда использование детерминированных тестов нецелесообразно и следует использовать случайные тесты. В работах [165], [163], [313], [194], [294] рассматриваются вопросы оценки длины случайных тестов и вероятности обнаружения неисправностей. Отметим принципиальную возможность использования вероятностного тестирования для обнаружения скрытых каналов в анализируемом оборудовании ([320], [197]).
В [13] и [14] рассматривается задача диагностики дискретного устройства со случайным входом в условиях, когда выходная последовательность устройства известна с искажениями.
В [310] рассматривается двоичный регистр сдвигов со случайным бернуллиевским входом, функция выходов которого известна с точностью до некоторого преобразования. Выходная последовательность регистра задана, а входная последовательность известна в вариантах. Построен статистический критерий проверки того, что выходная последовательность могла быть получена на данном варианте входной. Критерий основан на подсчете частот определенных биграмм в выходной последовательности.
Задачи, связанные с распознаванием выходных функций узлов защиты информации, в предположении, что эти функции являются пороговыми, рассматриваются в работах [282], [178] и др.
В главе рассматривается задача распознавания функции выходов по значению вероятности (или по частоте встречаемости) одного фиксированного слова в выходной последовательности.
Общая схема исследования выглядит следующим образом.
1. Вероятностные свойства случайной последовательности, перерабатываемой автоматом, описываются вектором действительных параметров, таких как набор вероятностей полиномиального распределения в случае независимых испытаний или элементов матрицы переходных вероятностей в случае марковских испытаний. Этот вектор может изменяться в некоторой области евклидова пространства подходящей размерности. Для фиксированного слова в выходном алфавите автомата вычислен предел его относительной частоты встречаемости в выходной последовательности, называемый вероятностной функцией. Вероятностная функция определена в указанной выше области евклидова пространства.
2. Две функции выходов конечного автомата, которые обладают одинаковой вероятностной функцией, названы статистически эквивалентными. Их нельзя различить по значению предела относительной частоты встречаемости данного слова. Введенное отношение эквивалентности описывается, приводятся оценки количества классов эквивалентности и мощностей этих классов.
3. Доказывается, что для всех точек области пространства, которой принадлежат параметры вероятностной схемы входной последовательности, за исключением множества нулевой меры, по значению предела относительной частоты наблюдаемого слова можно указать класс эквивалентности функции выходов.
4. Рассчитывается объем материала, необходимый для определения класса эквивалентности по статистике встречаемости наблюдаемого слова в выходной последовательности. Задача определения класса эквивалентности функции выходов приводится к виду дискретной минимизации модуля линейной формы.
Подчеркнем особенности рассматриваемой в первой главе задачи распознавания неизвестной функции выходов по вероятностным свойствам выходной последовательности, отделяющие ее от существующих постановок.
Во-первых, в рассматриваемой схеме имеется только одно «неизвестное» - функция выходов. Все остальные параметры автомата и «входного» распределения предполагаются известными.
Во-вторых, предполагается, что неизвестная функция выходов может быть произвольной.
В-третьих, предполагается известной вероятность (или частота встречаемости) какого-то одного слова в выходной последовательности.
Глава основана на следующих публикациях автора: [5], [22], [98-101], [240], [255], [257], [259], [260], [266], [276-278].
§ 1.1 Задача распознавания функции выходов автомата Мура, перерабатывающего последовательность независимых случайных величин
В параграфе рассматривается перерабатывающий последовательность независимых одинаково распределенных случайных величин сильносвязный автомат Мура. Вероятностной функцией для его функции выходов относительно слова у назван предел относительной частоты встречаемости слова у в растущих начальных отрезках выходной последовательности автомата А. Область определения вероятностной функции - множество всевозможных распределений на входном алфавите. На множестве функций выходов введено отношение статистической эквивалентности по признаку тождественного равенства их вероятностных функций. Рассматриваются задачи определения класса эквивалентности неизвестной функции выходов по значению вероятностной функции и по статистике выборочного среднего.
1.1.1 Вероятностная функция автомата
Пусть А = (X ,У, Q, к, /) - конечный детерминированный сильносвязный автомат Мура, где X = {хх, х2,..., хт} - входной алфавит, У = {ух, У2,..., Ук} - выходной алфавит, Q = {ч1,Ч2,..,Чг} - множество состояний, к: Q х X ^ Q - функция переходов, /: Q ^ У -
функция выходов. Пусть на множестве Q задано начальное вероятностное распределение
(0) ( (0) (0) (0)\ . ч =( ч ,ч ,. .,ч ), и на вход автомата А поступает последовательность независимых
случайных величин х^г), г = 1,2,... с распределением Р(х^г) = xj) = р],
т-1
р] > 0, ] = 1,2,...,т -1, рт = 1 р] > 0.
]=1
Автомату А , перерабатывающему последовательность х^^, i = 1,2,..., соответствует
автономный вероятностный автомат, определяемый квадратными матрицами М(у)= (т (у), У е Г) порядка г , где
т(у) = 2 Рх.
хеХ й( $ ,х Г ( 4 )=У
Пусть 7 = у(1) у(2)... у(/), у(г )еУ , / = 1,2,..., I. Положим, М = 2 М (у) , М (Л) = Е,
уе7
М(7) = М(у^1')М(у{2')..М(у(/'), где Л - пустое слово, Е - единичная матрица порядка г .
Через 7(7) обозначим сумму столбцов матрицы М(7), 7(7) = М(/)(11... 1)Г, где (11... 1)Г -
вектор-столбец из единиц порядка г .
Последовательность состояний автомата в рассматриваемой схеме образует
(0)
эргодическую цепь Маркова с вектором начального распределения q и матрицей переходных вероятностей М. Поэтому существует единственный стохастический вектор ж = (ж1,ж2,...,жг), такой, что тМ = ж. Вектор ж не зависит от . Усиленный закон больших чисел для цепей Маркова ([304], с. 61) позволяет интерпретировать величины ж и жг](у) как пределы относительных частот встречаемости состояния qi и слова 7 в растущих начальных отрезках последовательности состояний и выходной последовательности автомата А соответственно.
Проведенные построения относятся к вектору р = (р,р2,...,ри_х), принадлежащему открытой связной области
Г т-1 |
О = \р = (р1,Р2,...,Рт-1) , 2 Р] < 1, Р1 > 0, 1 = 1,2,..., т - 1 |
евклидова пространства Кт-1. В частности, для т = 2 (случай автомата с двоичным входным алфавитом и бернуллиевской входной последовательности с распределением Р {1} = р1,
Р {0} = р0, р0 + рх = 1, р0 > 0, рх > 0 ) вектора ж и 7(7) являются функциями одной
действительной переменной р1. Функция р(р)=Ж7(у) называется ([160]) вероятностной функцией автомата А для слова 7.
Лемма 1.1. Вероятностная функция автомата А для слова 7 может быть представлена
как отношение двух полиномов от р = (р,р2,...,ри_с целыми коэффициентами
ру( p)
21
3(p)
5 (p) •
где знаменатель 5 (р) не зависит от у, степени числителя и знаменателя ограничены
числами г +1 и г соответственно: 0 < 5 (р) < г, 0 < ёе§ Щ (р)< г +1, где I - длина слова у.
Доказательство. Элементы матрицы М являются линейными функциями от р с целыми коэффициентами. Согласно правилу Крамера для системы линейных уравнений жМ = ж, каждый из ж ■ представим в виде отношения двух полиномов с целыми коэффициентами, степени которых не превосходят г . Знаменатели этих отношений не зависят от 7 .
Элементы матрицы М(у) являются полиномами от р степеней не выше I. Следовательно, координаты вектора ^(у)= М(у)(11... 1) обладают тем же свойством.
Поскольку Р (рр)=ж7](у), лемма доказана. ■
В [220] имеется описание вероятностных функций сильносвязных автоматов с двоичными входным и выходным алфавитами для случая I = 1.
Теорема 1.2 ([220]). Пусть I = 1. Функция О (р) является вероятностной функцией для
знака сильносвязного автомата тогда и только тогда, когда она удовлетворяет условиям:
1) О (р) определена на интервале (0,1) и принимает значения из отрезка [0,1];
2) функция О (р) представима в виде Q (р)/5 (р) , где Q (р) и 5 (р ) - полиномы с целыми коэффициентами, 5 (р) > 0 при р е (0,1);
3) если О (р) принимает значение 0 или 1 внутри интервала, то она является тождественной константой. ■
1.1.2 Задача распознавания функции выходов. Статистическая эквивалентность
Пусть А = {А = (X,У,Q,к,/), / е ¥г к} - класс описанных выше конечных
сильносвязных автоматов Мура, функции выходов которых принадлежат множеству Рг^к всех функций из Q в У .
Рассмотрим возможность распознавания неизвестной функции выходов / автомата А еА по значению его вероятностной функции р (р) для заданного р е Б. С целью подчеркнуть зависимость вероятностной функции от / будем обозначать ее р у (р).
Функции /1 и /2 из рк назовем статистически эквивалентными относительно слова у е У (и примем для такого случая обозначение / « /2), если р у (р) = р у (р) для всех
р е Б. Введенное отношение является отношением эквивалентности, разбивающим рк на
Похожие диссертационные работы по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Автоматные методы распознавания речи2001 год, кандидат физико-математических наук Мазуренко, Иван Леонидович
Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей на основе клеточных автоматов2011 год, кандидат технических наук Сухинин, Борис Михайлович
Разработка и исследование методов моделирования и оценки мер тестопригодности логических схем2000 год, кандидат технических наук Голубева, Ольга Ивановна
Геометрические образы поведения автоматов1999 год, кандидат физико-математических наук Тяпаев, Ливат Борисович
Построение и анализ эффективности алгоритмов обращения дискретных функций в математических моделях информационной безопасности2019 год, доктор наук Логачев Олег Алексеевич
Список литературы диссертационного исследования доктор наук Мельников Сергей Юрьевич, 2021 год
БИБЛИОГРАФИЯ
1. Abainia K., Ouamour S., Sayoud H. Robust Language Identification of Noisy Texts: Proposal of Hybrid Approaches // In 25th International Workshop on Database and Expert Systems Applications, DEXA 2014, Munich, Germany, September 1-5, 2014, IEEE, 2014. — Pp. 228-232.
2. Abainia K., Ouamour S., Sayoud H. Effective language identification of forum texts based on statistical approaches // Inf. Process. Manag. — 2016. — V. 52. — Pp. 491-512.
3. Abiad A., Cioaba S.M., Tait M. Spectral bounds for the k-independence number of a graph // Linear Algebra and Appl. — 2016. — V. 510. — Pp. 160-170.
4. Ablow C.M., Brenner J.L. Roots and canonical forms for circulant matrices // Trans. Amer. Math. Soc. — 1963. — V. 107, no. 2. — Pp. 360-376.
5. Adamu A., Shorgin V., Melnikov S., Gaidamaka Y. Flexible Random Early Detection Algorithm for Queue Management in Routers Traffic // DCCN 2020. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12563 LNCS. — 2020. — Pp. 196-208.
6. Aharoni R., Koppel M., Goldberg Y. Automatic Detection of Machine Translated Text and Translation Quality // Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics. — 2014. —Vol. 2. — Pp. 289-295.
7. Aikawa T., Melero M., Schwartz L., Wu A. Multilingual Sentence Generation // In Proceedings of 8th European Workshop on Natural Language Generation. — 2001. — Pp. 57-63.
8. Alhakim A. On the eigenvalues and eigenvectors of an overlapping Markov chain // Probab. Theory Related Fields. — 2004. — V. 128(4). — Pp. 589-605.
9. Allouche J.-P., Shallit J. Automatic Sequences. Theory, Applications, Generalizations. — Cambridge University Press. — 2003. — 571 p.
10. Anashin V.S. The non-archimedean theory of discrete systems // Mathematics in Computer Science. — 2012. — Vol. 6, no. 4. — Pp. 375-393.
11. Anashin V.S., Khrennikov A.U. Applied Algebraic Dynamics. Berlin, de Gruyter Expositions in Mathematics. — 2009. — 558 p.
12. Arpith C. Jacob, Maya Gokhale. Language classification using n-grams accelerated by FPGA-based Bloom filters // Proceedings of the 1st international workshop on High-performance reconfigurable computing technology and applications, HPRCTA. — 2007. — Pp. 31-37.
13. Athanasopoulou E., Hadjicostis C.N. Probabilistic approaches to fault detection in networked discrete event systems // IEEE Trans. Neural Networks. — Vol. 16, no. 5. — 2005. — Pp. 1042-1052.
14. Athanasopoulou E., Lingxi L., Hadjicostis C.N. Probabilistic failure diagnosis in finite state machines under unreliable observations // in Proceedings of the 8th International Workshop on Discrete Event Systems — WODES'06, Ann Arbor, MI. — 2006. — Pp. 301-306.
15. Ayyer A., Strehl V. Stationary distribution and eigenvalues for a de Bruijn process // In: Kotsireas, I.S., Zima, E.V. (eds.) Advances in Combinatorics, pp. 101 -120. Springer, Berlin (2013).
16. Bangalore S., Rambow O. Exploiting a probabilistic hierarchical model for generation // In Proceedings of the 18th International Conference on Computational Linguistics (COLING'OO). — 2000. — Pp. 42-48.
17. Bangalore S., Rambow O., Whittaker S. Evaluation metrics for generation // In Proceedings of the 1st International Conference on Natural Language Generation (INLG '00). — 2000. — Pp. 1-8.
18. Barman U., Das A., Wagner J., Foster J. Code Mixing: A Challenge for Language Identification in the Language of Social Media // Proceedings of The First Workshop on Computational Approaches to Code Switching, October 25, 2014, Doha, Qatar. — 2014. — Pp. 13-23.
19. Basavaraja S.V., Screenivas T.V. Low Complexity LID using Pruned Pattern Tables of LZW // In INTERSPEECH-2006. — 2006. — Pp. 413-416.
20. Belz A. Statistical generation: Three methods compared and evaluated // In: Proceedings of the 10th European Workshop on Natural Language Generation (ENLG'05). — 2005. — Pp. 15-23.
21. Bermond J.C., Peyrat C. De Bruijn and Kautz Networks: A competitor for the Hypercube? // European Workshop on Hypercubes and Distributed Computers, Elsevier. — 1989. — Pp. 279-293.
22. Beschastnyi1 V., Ostrikova D., Melnikov S., Gaidamaka Y. Modelling Multi-connectivity in 5G NR Systems with Mixed Unicast and Multicast Traffic // DCCN 2020. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12563 LNCS. — 2020. — Pp. 52-63.
23. Bhadri R., Vishnu V.B., Naidu G.A., Pratap R.L., Vinaya B.A. Effect of Language Complexity on Deciphering Substitution Ciphers - A Case Study on Telugu // International Journal of Security and Its Applications. — 2010. — Vol. 4, no. 1. — Pp. 11-20.
24. Brodic D., Amelio A., Milivojevic Z.N. Characterization and distinction between closely related south Slavic languages on the example of Serbian and Croatian // Proc. of the 16th International Conference on Computer Analysis of Images and Patterns CAIP 2015, Valletta, Malta, Part I, LNCS 9256. — 2015. — Pp.654-666.
25. Brouwer A.E., Haemers W.H. Spectra of Graphs. Springer, New York. — 2012. — 245 p.
26. Bryant P.R., Christensen J. The enumeration of shift register sequences // Journ. of Comb. Theory. — 1983. — Ser. A, v.35. — Pp.154-172.
27. Bryant R.D. Covering the de Bruijn graph. Thesis. — Monterey, California. — Naval Postgraduate School. — 1983. — 113 p.
28. Bryant R.D., Fredricksen H. Covering the de Bruijn graph // Discrete Math. — 1991. — V. 89. — Pp. 133-148.
29. Busch A., Boles W., Sridharan S. Texture for Script Identification // IEEE Transactions on Pattern Analysis and Machine Intelligence. — November 2005. — v. 27, no. 11, Pp. 1720-1732.
30. Campbell W., Gleason T., Navratil J., Reynolds D., Shen W., Singer E., Torres-Carrasquillo P. Advanced language recognition using cepstra and phonotactics: MITLL system performance on the NIST 2005 language recognition evaluation // In Proc. IEEE Odyssey 2006: The Speaker and Language Recognition Workshop (San Juan, Puerto Rico). — June 2006.
31. Cardenosa J., Gallardo C., Tovar E. Standardization of the generation process in a multilingual environment // in: Convergences'03, International Conference on the Convergence of Knowledge, Culture, Language and Information Technologies 2003, Alexandria, EGYPT. — 2003.
32. Caropreso M.F., Inkpen D., Khan S., Keshtkar F. Novice-friendly natural language generation template authoring environment // In Proceedings of the 22nd Canadian Conference on Artificial Intelligence: Advances in Artificial Intelligence, Canadian AI'09, 195-198. Berlin, Heidelberg: Springer-Verlag. — 2009.
33. Carter S., Weerkamp W., Tsagkias M. Microblog language identification: overcoming the limitations of short, unedited and idiomatic text // Language Resources and Evaluation. — 2013. — Vol. 47, no. 1. — Ppp. 195-215.
34. Cartwright D.A., Cueto M.A., Tobis E.A. The Maximum Independent Sets of de Bruijn Graphs of Diameter 3 // Electronic Journal of Combinatorics. — 2011. — Vol. 18. — P. 194.
35. Cavnar W., Trenkle J. N-Gram based text categorization // In Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval. — 1994. — Pp. 161-175.
36. Chatterjee K., Doyen L., Edelsbrunner H., Henzinger T.A. & Rannou P. Mean-Payoff Automaton Expressions // In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS. Springer, Heidelberg. — 2010. — Vol. 6269. — Pp. 269-283.
37. Chen S.F., Goodman J. An Empirical Study of Smoothing Techniques for Language Modeling // Computer science group, Harvard University, Cambridge, Massachusetts, TR-8-98, August, 1998.
38. Chen W.-K. The VLSI Handbook, Second Edition. — CRC Press. — Chicago. — 2006. — 2320 p.
39. Chepovskiy A., Gusev S., Kurbatova M. Language identification for texts written in transliteration // in: CDUD 2012 — Concept Discovery in Unstructured Data / Ed.: S. O. Kuznetsov, D. I. Ignatov, J. Poelmans. Leuven : Katholieke Universiteit Leuven. — 2012. — Pp. 13-20.
40. Clark A., Dawson E. Optimization Heuristics for the Automated Cryptanalysis of Classical Ciphers // J. of Comb. Math. and Comb. Comp., 28. — 1998. — Pp. 63-86.
41. Clifford A. H., Preston G. B. The Algebraic Theory of Semigroups. Vol. 1. AMS Publ. — 1964. — 224 p.
42. Compeau P., Pevzner P., Tesler G. How to apply de Bruijn graphs to genome assembly // Nature Biotechnology. — 2011. — V. 29. — Pp. 987-991.
43. Cusick T.W., Fredricksen H., Stanica P. On the delta sequence of the Thue-Morse sequence // Australas. J. Comb. — 2007, 39. — P. 293-300.
44. Davis A.S. Markov Chains as Random Input Automata // The American Mathematical Monthly. — 1961. — Vol. 68, no. 3. — Pp. 264-267.
45. Delorme C., Tillich J.-P. The spectrum of de Bruijn and Kautz graphs // European Journal of Combinatorics 19. — 1998. — Pp. 307-319.
46. Du D. Z., Hwang F. K. Generalized de Bruijn digraphs // Networks 18 (1). — 1988. — Pp. 2738.
47. DuBay W.H. The Principles of Readability // Costa Mesa, CA: Impact Information. — 2004.
— 77 p.
48. Dupont P., Denis F., Esposito Y. Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms // Pattern Recognition 38.
— 2005. — Pp. 1349-1371.
49. Etzion T. An algorithm for generating shift - register cycles // Theor. Comp. Sci. — 1986. — V. 44. — Pp. 209-224.
50. Freudenthal H. Lincos: Design of a Language for Cosmic Intercourse // North-Holland, Amsterdam. — 1960. — 224 p.
51. Ghosh D., Dube T., Shivaprasad A.P. Script Recognition - A Review // IEEE, Transactions on Patter Analysis and Machine Intelligence, 32 (12). — 2010. — Pp. 2142-2161.
52. Golomb S. W. Shift Register Sequences — a Retrospective Account (SETA'06). SpringerVerlag, Berlin, Heidelberg. — 2006. — Pp. 1-4.
53. Golomb S. W. Shift Register Sequences. Secure and Limited-Access Code Generators, Efficiency Code Generators, Prescribed Property Generators, Mathematical Models (3rd revised edition). World Scientific, Singapore. — 2017. — 259 p.
54. Hadjicostis C.N. Probabilistic detection of FSM single state-transition faults based on state occupancy measurements // IEEE Trans. Autom. Contr. — 2005. — 50, no. 12. — Pp. 2078-2083.
55. Hamlet D. When only random testing will do // in Random Testing, J. Mayer and R. G. Merkel, Eds. — ACM. — 2006. — Pp. 1-9.
56. Haramoto, H., Matsumoto, M. Again, random numbers fall mainly in the planes: xorshift128+ // arxiv.org/abs/1908.10020. — 2020.
57. Heuberger C. On planarity and colorability of circulant graphs // Discrete Mathematics. — 2003. — Vol. 26. — Pp. 153-169.
58. Hochberg J., Bowers K., Cannon M., Kelly P. Script and language identification for handwritten document images // International Journal on Document Analysis and Recognition. — 1999. — Vol. 2. — Pp. 45-52.
59. Hong Y.P., Horn R.A. On simultaneous reduction of families of matrices to triangular or diagonal form by unitary congruence // Linear and multilinear algebra. — 1985. — V. 17, no. 3-4. — Pp. 271-288.
60. Hosseinabady M., Kakoee M.R., Mathew J., Pradhan D.K. De Bruijn graph as a low latency scalable architecture for energy efficient massive NoCs // Proc. Conf. on Design, automation and test in Europe, Munich. — 2008. — Pp. 1370-1373.
61. Humphreys K., Caleagno M., Weise D. Reusing a statistical language model for generation // In Proc. of the 8th European Workshop on Natural Languag e Generation (EWNLG'01). — 2001. — Pp. 86-91.
62. Imase M., Itoh M. Design to minimize diameter on building-block networks // IEEE Trans. Comput. — 1981. — Vol. 30. — Pp. 439-442.
63. Imase M., Itoh M. A design for directed graphs with minimum diameter // IEEE Trans. Comput. — 1983. — Vol.32. — Pp. 782-784.
64. Iskhakova A., Kruglova S., Melnikov S., Sidorov E. The Approach to Minimize the Impostor Method Errors in the Author Identification Open Problem // Proceedings of the R. Piotrowski's Readings in Language Engineering and Applied Linguistics. S.Petersburg, Russia. — November 27, 2019. — CEUR Workshop Proceedings, V. 2552. — Pp. 60-72.
65. Ito H., Amari S.-I., Kobayashi K. Identifiability of hidden Markov information sources and their minimum degrees of freedom // IEEE Trans. Inf. Theory. — 1992. — Vol. 38(2). — Pp. 324333.
66. Johnson D. B. Finding All the Elementary Circuits of a Directed Graph // SIAM Journal of Computing 4. — 1975. — Pp. 77-84.
67. Johnson D.M., Mendelson N.S. Planarity properties of the Good — de Bruijn graphs // Comb. structures and its appl. Proc. Calgary Intern. Conf., Calgary, 1969. — N.Y. Gordon and Breach, 1970.
— Pp. 177-183.
68. Jurafsky D., Martin J.H. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition (2ed.). Prentice Hall, USA.
— 2009. — 1044 p.
69. Jyotsna B., Murthy H.A., Nagarajan T. Language identification from short segments of speech // ICSLP 2000, Beijing, China. — 2000. — Pp. 1033-1036.
70. Kanazawa K., Kemmotsu K., Mori Y., Aibe N., Yasunaga M. High-Speed Calculation of Convex Hull in 2D Images Using FPGA // in: Parallel Computing with FPGAs, held in conjunction with ParCo 2015 (ParaFPGA 2015), Edinburgh, Scotland, UK. — 2015. — Pp. 533-542.
71. Kant S., Verma V., Verma N., Dass B.K. Identification scheme for romanized Indian languages from their plain and ciphered bit stream // J. Disc. Math. Sci. Crypt. 13(4). — 2010. — Pp. 329-345.
72. Karasimos A., Isard A. Multi-lingual Evaluation of a Natural Language Generation System // In Proceedings of the Fourth International Conference on Language Resources and Evaluation (LREC 2004), Lisbon, Portugal. — May 2004. — Pp. 829-832.
73. Kastner C.M., Covington G.A., Levine A.A., Lockwood J.W. HAIL: A hardware-accelerated algorithm for language identification // In 15th Annual Conference on Field Programmable Logic and Applications (FPL), Tampere, Finland. — Aug. 2005. — Pp.499-504.
74. Katz S.M. Estimation of probabilities from sparse data for the language model component of a speech recognizer // IEEE Transactions on Acoustics, Speech and Signal Processing, 35(3). — 1987.
— Pp. 400-401.
75. Keane M. Generalized Morse sequences // Z. Wahrscheinlichkeitstheorie verw. Geb. — 1968.
— V.10. — Pp. 335-353.
76. Khapra M. M., Joshi S., Ramanathan A., Visweswariah K. Offering Language Based Services on Social Media by Identifying User's Preferred Language(s) from Romanized Text // Proceedings of the 22nd International World Wide Web Conference, vol. Companion, Rio de Janeiro, Brazil. — May, 2013. — Pp. 71-72.
77. Kikuchi Y., Shibata Y. On the independent set of de Bruijn graphs // IEIC Technical Report (Institute of Electronics, Information and Communication Engineers). — 2001. — Vol. 101, no. 133.
— Pp. 25-32.
78. Kipyatkova I., Karpov A. Recurrent Neural Network-based Language Modeling for an Automatic Russian Speech Recognition System // Proceedings of International Conference AINL-ISMW FRUCT 2015. — 2015. — Pp. 33-38.
79. Kirchhoff K., Parandekar S. Multi-stream statistical language modeling with application to automatic language identification // Proceedings of Eurospeech-01. — 2001. — Pp.803-806.
80. Koolagudi S.G., Rao K.S. Emotion recognition from speech: a review // International Journal of Speech Technology. — 2012. — Vol. 15. — Pp. 99-117.
81. Kulay A.Y., Melnikov S.Y. Different approaches to the garbled text language recognition, using the data compression methods // Proc. XII Intern. Conference "Speech and Computer" 15-18 Oct. 2007, Moscow. — 2007. — Vol. 2. — Pp. 697-701.
82. Lam L., Ding J., Suen C.Y. Differentiating between oriental and European scripts by statistical features // International Journal of Pattern Recognition and Artificial Intelligence. — 1998. Vol. 12. — Pp. 63-79.
83. Langkilde I. Forest-based statistical sentence generation // In Proceedings of the 6th Applied Natural Language Processing Conference and the 1st Meeting of the North American Chapter of the Association of Computational Linguistics (ANLP-NAACL'00). — 2000. — Pp. 170-177.
84. Langkilde I., Knight K. Generation that exploits corpus-based statistical knowledge // Proceedings of the COLING-ACL. — 1998. — Pp. 704-710.
85. Langkilde I., Knight K. The practical value of N-grams in generation // Proceedings of the 9th International Natural Language Workshop (INLG'98), Niagara-on-the-Lake, Ontario. — 1998. — Pp. 248-255.
86. Lewis M.P., Simons G.F., Fennig C.D. (eds.) Ethnologue: Languages of the World, Eighteenth edition. Dallas, Texas: SIL International. — 2021. Online version: http://www. ethnolo gue.com.
87. Li B., Zhang C., Li B., Jiang H., Xu Q. A hardware-efficient parallel architecture for real-time blob analysis based on run-length code // J. of Real-Time Image Proc. — September 2017. — Pp. 116.
88. Lichiardopol N. Independence number of de Bruijn graph // Discrete Mathematics. — 2006. — Vol. 306, I. 12. — Pp. 1145-1160.
89. Liu H., Wang J. A new way to enumerate cycles in graph // In AICT-ICIW'06: Proceedings of the Advanced Int'l Conference on Telecommunications and Int'l Conference on Internet and Web Applications and Services, Washington, DC, USA. — 2006. — Pp. 57-59.
90. Liu M. Homomorphisms and automorphisms of 2-D de Bruijn-Good graphs // Discrete Mathematics. — 1990. — Vol. 85, I. 1. — Pp. 105-109.
91. Loguinov D., Kumar A., Rai V., Ganesh S. Graph-theoretic analysis of structured peer-to-peer systems: Routing distances and fault resilience // ACM SIGCOMM. — 2003. — Pp. 395-406.
92. Majer P., Novaga M. Infinite paths in random shift graphs // Dipartimento di Matematica, Universif a di Padova. — 2012. — arXiv:0906.1689v3.
93. Malyutov M. Authorship Attribution of Texts: A Review // Information Transfer and Combinatorics, LNCS 4123. — 2006. — Pp. 362-380.
94. Marcu D., Carlson L., Watanabe M. An Empirical Study in Multilingual Natural Language Generation: What Should A Text Planner Do? // In Proceedings of the 1 st International Conference on Natural language Generation (INLG'00). — 2000. — Pp. 17-23.
95. Marsaglia G. Random Numbers Fall Mainly in the Planes // Proceedings of National Academy of Sciences, 61. — 1968. — Pp. 5-28.
96. Matthews R.A.J. The use of genetic algorithms in cryptanalysis // Cryptologia, 17(4). — 1993. — Pp. 187-201.
97. Melnikov S.Yu. The Spectra of Undirected de Bruijn Graphs and an Upper Bound for Their Independence Numbers // Discrete Mathematics and Applications 5(6). — 1995. — Pp. 535-539.
98. Melnikov S.Yu. Stationary Distribution of Random Walk on the Generalized de Bruijn Digraphs // II International Baltic Symposium on Applied and Industrial Mathematics (BISAIM 2016), Svetlogorsk, June 12-18, 2016, Review of Applied and Industrial Mathematics, 5(23) . — 2016. — Pp. 185-186.
99. Melnikov S.Yu., Samouylov K.E. The Recognition of the Output Function of a Finite Automaton with Random Input // In: Vishnevskiy V., Kozyrev D. (eds) Distributed Computer and Communication Networks DCCN 2018. Communications in Computer and Information Science, Springer. — 2018. — Vol. 919. — Pp. 525-531.
100. Melnikov S.Yu., Samouylov K.E. Probabilistic functions and statistical equivalence of binary shift registers with random Markov input // Proceedings of the Workshop on information technology and scientific computing in the framework of the X International Conference Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems (ITTMM 2020). Moscow, CEUR Workshop Proceedings. — 2020. — V.2639. — Pp. 93-99.
101. Melnikov S.Yu., Samouylov K.E. On recognition of the shift register output function with a random input for a Markov model of an input sequence // Proceedings of the Workshop on information technology and scientific computing in the framework of the X International Conference Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems (ITTMM 2020). Moscow, CEUR Workshop Proceedings. . — 2020. — V. 2639. — Pp. 100-107.
102. Melnikov S.Yu., Samouylov K.E. Polyhedra of Finite State Machines and their Use in the Identication Problem // In: Galinina O., Andreev S., Balandin S., Koucheryavy Y. (eds) Internet of Things, Smart Spaces, and Next Generation Networks and Systems. NEW2AN 2020, ruSMART 2020. Lecture Notes in Computer Science, Springer, Cham. — 2020. — V. 12526. — Pp. 110-121.
103. Melnikov S.Yu., Samouylov K.E. Cesaro Sequences and Cesaro Hereditary Automata //In: Galinina O., Andreev S., Balandin S., Koucheryavy Y. (eds) Internet of Things, Smart Spaces, and Next Generation Networks and Systems. NEW2AN 2020, ruSMART 2020. Lecture Notes in Computer Science, Springer, Cham. . — 2020. — V. 12526. — Pp. 259-269.
104. Melnikov S.Yu., Samouylov K.E. Polygons characterizing the joint statistical properties of the input and output sequences of the binary shift register // ICFNDS'20: The 4th International Conference on Future Networks and Distributed Systems, November 2020. — Article No.: 10. — Pp. 1-6.
105. Melnikov S.Yu., Samouylov K.E. Cesaro-heredity property in the shift register family // Материалы XXIII международной научной конференции DCCN 2020, ред. В. М. Вишневский, К. Е. Самуйлов. — Pp. 751-763.
106. Mikolov T., Karafi'at M., Burget L., Cernock'y J., Khudanpur S. Recurrent neural network based language model // in Proceedings of Interspeech. — 2010. — Pp. 1045-1048.
107. Milkowski M. Explaining the Computational Mind. MIT Press. — 2013. — 243 p.
108. Moffat A. Implementing the PPM data compression scheme // IEEE Transactions on Communications. — 1990. — Vol. 38(11). — Pp. 1917-1921.
109. Morrison K.E. A Generalization of Circulant Matrices for Non-Abelian Groups // Tech.rep. California Polytechnic State University. — 1988.
110. Muchnik A., Pritykin Y., Semenov A. Sequences close to periodic // Russian Mathematical Surveys. — 2009. — Vol. 64(5). — Pp. 805-871.
111. Mykkeltveit J. A proof of Golomb's conjecture for the de Bruijn graph // J. of comb. theory. Ser. B. — 1972. — V. 13. — Pp. 40-45.
112. Nguyen D., Dogruoz A.S. Word Level Language Identification in Online Multilingual Communication // EMNLP 2013: Conference on Empirical Methods in Natural Language Processing . — Seattle, US. — 2013. — Pp. 857-862.
113. Obaidullah S.M., Anamika Mondal, Nibaran Das, Kaushik Roy. Script Identification from Printed Indian Document Images and Performance Evaluation Using Different Classifiers // Applied Computational Intelligence and Soft Computing. Volume 2014 (2014), Article ID 896128.
114. Pavan K., Tandon N., Verma V. Addressing challenges in automatic language identification of romanized text // Proceedings of IC0N-2010: 8th International Conference on Natural Language Processing, Macmillan Publishers, India.
115. Paz A. Introduction to probabilistic automata. Academic Press, London. — 1971. — 228 p.
116. Peake G.S., Tan T.N. Script and Language Identification from Document Images // Workshop on Document Image Analysis. — 1997. — Pp. 10-17.
117. Potapova R.K., Potapov V.V. The mechanisms of Russian-German speech communication and code-switching // Вестник МГЛУ. Выпуск 13 (673). — 2013. — C. 9-18.
118. Prasanthkumar P.V., MidhunT.P., Archana Kurian. A survey on Script and Language identification for Handwritten document images // IOSR Journal of Computer Engineering (IOSR-JCE), Vol. 17, I. 2. — 2015. — Pp. 105-109.
119. Putnam H. Psychological Predicates. In: Capitan and Merill (eds) Art, Mind&Religion. Pittsburgh, 1967. Reprinted as The Nature of Mental States in Rosenthal D. (ed.) The Nature of Mind. Oxford: Oxford University Press. — 1991. — Р. 223-230. Перевод на рус яз.: Патнэм Х.
Психологические предикаты (Природа ментальных состояний) // Патнэм Х. Философия сознания. М.: Дом интеллектуальной книги, 1999. — C. 53-67.
120. Ranaivo-Malan9on B. Automatic Identification of Close Languages - CaseStudy: Malay and Indonesian // ECTI Transaction on Computer and Information Technology, 2 (2). — 2006. — Pp. 126133.
121. Reddy S.M., Pradham D.K., Kuhl J.G. Directed graphs with minimum diameter and maximal connectivity // Tech. Rep. School Eng. Rochester, Oakland Univ., 1980.
122. Reiter E., Dale R. Building Natural Language Generation Systems // Cambridge University Press, Cambridge. — 2000. — 272 p.
123. Rescorla M. The Computational Theory of Mind // The Stanford Encyclopedia of Philosophy (Spring 2017 Edition), Edward N. Zalta (ed.), https://plato.stanford.edu/entries/computational-mind.
124. Rosenfeld R. Two decades of statistic language modeling: where do we go from here? // in Proceedings of the IEEE. — 2000. — Vol. 88, I. 8. — Pp. 1270-1278.
125. Saxena P.K., Yadav P., Mishra G. Index of Garbledness for Automatic Recognition of Plain English Texts // Defence Science Journal. — 2010. — Vol. 60, no. 4. — Pp. 415-419.
126. Scott D., Evans R. Multilingual Document Management without Translation // ELSNEWS: The newsletter of the European Network in Language and Speech 7. — 1998. — Pp 2-3.
127. Sequiera R.D., Rao S.S., Shambavi B. R. Word-Level Language Identification and Back Transliteration of Romanized Text // Proc. of the Forum for Information Retrieval Evaluation FIRE '14, Bangalore, India. — 2014. — Pp. 70-73.
128. Shen W., Campbell W.M., Gleason T. Experiments with Lattice-based PPRLM Language Identification // Proc. Odyssey - The Speaker and Language Recognition Workshop. — 2006. — Pp. 1-6.
129. Sibun P, Spitz A.L. Language determination: natural language processing from scanned document images // In: 4th Applied Natural Language Processing conference (ANLP). — 1994. — Pp. 15-21.
130. Siegenthaler T., Kleiner A., Forre R. Generation of binary sequences with controllable complexity and ideal r-tuple distribution // in Advances in Cryptology — Eurocrypt'87, LNCS 304. — 1987. — Pp.15-23.
131. Skala V. Point-in-Convex Polygon and Point-in-Convex Polyhedron Algorithms with O(1) Complexity using Space Subdivision // ICNAAM 2015, AIP Publishing LLC. — 2015. — Pp. 22-28.
132. Sloane A., Plouffe S. The Encyclopedia of Integer Sequences, Academic Press. — 1995. — 587 p.
133. Spielman D.A. Spectral graph theory and its applications // In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer. Providence, USA. — 2007. — Pp. 29-38.
134. Spillman R., Janssen M., Nelson B., Kepner M. Use of a Genetic Algorithm in the Cryptanalysis of Simple Substitution Ciphers // Cryptologia, 17(1). — 1993. — Pp. 31-44.
135. Sripada S., Reiter E., Hawizy L. Evaluation of an NLG system using post-edit data: Lessons learned // In Proceedings of ENLG. — 2005. — Pp. 133-139.
136. Tatarakis N., Kavallieratou E. Language Identification by Using SIFT Features // International Journal of Advanced Research in Artificial Intelligence. — 2015. — Vol. 4, no.12. — Pp. 34-43.
137. Tee G.J. Eigenvectors of block circulant and alternating circulant matrices // Res. Lett. Inf. Math. Sci. — 2005. — Vol. 8. — Pp. 123-142.
138. Tromp E., Pechenizkiy M. Graph-Based N-gram Language Identification on Short Texts // In Proc. 20th Machine Learning conference of Belgium and The Netherlands. — 2011. — Pp. 27-35.
139. Vidyasagar M. The complete realization problem for hidden Markov models: a survey and some new results // Math. Control Signals Syst. — 2011. — Vol. 23. — Pp. 1-65.
140. Vogel J., Tresner-Kirsch D. Robust Language Identification in Short, Noisy Texts: Improvements to LIGA // In Proceedings of the Third International Workshop on Mining Ubiquitous and Social Environments (MUSE 2012). — 2012. — Pp. 43-50.
141. Voss C., Tratz S., Laoudi J., Briesch D. Finding Romanized Arabic Dialect in Code-Mixed Tweets // Proceedings of the 9th International Conference on Language Resources and Evaluation. — 2014. — Pp. 188-199.
142. Wan Z.X., Xiong M.A., Yu R.H. On the number of cycles of short length in the de Bruijn-Good graph Gn // Discrete Math. —1986. — Vol. 62. — Pp. 85-98.
143. Weiner J., Vu N.T., Telaar D., Metze F., Schultz T., Lyu D.-C., Chng E.-S., Li H. Integration of language identification into a recognition system for spoken conversations containing code-switches // Proceedings of the Third International Workshop on Spoken Languages Technologies for Underresourced Languages, Cape Town, South Africa, SLTU 2012.
144. Wolfhram S. The Mathematica Book, 5th ed. Wolfram Media Inc. — 2003. — 1488 p.
145. Xueliang Li, Fuji Zhang. On the numbers of spanning trees and Eulerian tours in generalized de Bruijn graphs // Discrete Math. — 1991. — Vol. 91. — Pp. 189-197.
146. Yao-Kun Wu, Rui-Zhong Jia, Qiao Li. g-circulant solutions to the (0, 1) matrix equation Am = Jn // Linear Algebra and Appl. — 2002. — Vol. 345. — Pp. 195-224.
147. Zhang C., Hansen J.H.L. Analysis and classification of speech mode: Whisper through shouted // Proc. Interspeech 2007. — 2007. — Pp. 2289-2292.
148. Zhi-Guo Deng, Bao-Gen Xu. The Independence Number for De Bruijn networks and Kautz networks // Discrete Appl. Math. — 2008. — Vol. 156, Issue 15. — Pp. 3035-3039.
149. Zhou Jin-tu. The diagonalization condition for g-circulant matrix // Zhejiang Norm. Univ. Natur. Sci. — 2004. — Vol. 27, no. 4. — Pp. 325-328.
150. Zhu G., Yu X., Li Y., Doermann D. Language identification for handwritten document images using a shape codebook // Pattern Recognition. — 2009. — Vol. 42(12). — Pp. 3184-3191.
151. Zissman M.A. Comparison of Four Approaches to Automatic Language Identification of Telephone Speech // IEEE Transactions on Speech and Audio Processing. — 1996. — Vol. 4, no. 1. — Pp. 31-44.
152. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии: учебное пособие. — М. : Гелиос АРВ, 2002. — 480 c.
153. Арутюнов А.А., Борисов Л.А., Зенюк Д.А., Ивченко А.Ю., Кирина-Лилинская Е.П., Орлов Ю.Н., Осминин К.П., Федоров С.Л., Шилин С.А. Статистические закономерности европейских языков и анализ рукописи Войнича // Препринты ИПМ им. М.В. Келдыша. — 2016, № 52. — 36 с.
154. Бабаш А.В. О периодичности последовательности состояний автомата, отвечающей начальносму состоянию и входной периодической последовательности // Дискрет. матем. — т. 14, вып. 2. — 2002. — С. 54-64.
155. Бабаш А.В. Запреты автоматов и двоичных функций // Тр. по дискр. матем., том 9. — 2006. — С. 7-20.
156. Бабаш А.В. Запреты автоматов // Матем. заметки, том 91, выпуск 5. — 2012. — С. 667673.
157. Бабин Д.Н., Холоденко А.Б. Об автоматной аппроксимации естественных языков // Интеллектуальные системы, т. 12, № 3. — 2008. — С. 125-136.
158. Бабин Д.Н., Пархоменко Д.В. О мультимножестве выходных слов конечного автомата // Интеллектуальные системы. Теория и приложения, т. 20, № 3. — 2016. — С. 101-102.
159. Балакин Г.В., Никонов В.Г. Псевдобулевы методы решения систем нелинейных булевых уравнений // Обозрение прикладной и промышленной математики, т. 23, вып. 4. — 2014. — С. 1-4.
160. Барашко А.С. О статистической эквивалентности автоматов по входу и выходу // Автомат. и телемех., вып. 9. — 1987. — С. 144-150.
161. Барашко А.С. О ранге и статистическом отображении сильносвязного автомата // Кибернетика, № 4. — 1987. — С. 56-60.
162. Барашко А.С. О распознавании автоматов с использованием генераторов зависимых случайных сигналов // Науковi пращ Донецького нащонального техшчного ушверситету. Серiя «Проблеми моделювання та автоматизацп проектування» (МАП-2002). Випуск: 52. — Донецьк : ДонНТУ, 2002. — 248 с. — С. 61-71.
163. Барашко А.С. Оценки функции вероятности обнаружения неисправности дискретного устройства // Науковi пращ Донецького нащонального техшчного ушверситету, серiя
«1нформатика, юбернетика та обчислювальна техшка», вып. 93. — Донецк : ДонНТУ, 2005. — С.167-174.
164. Барашко А.С., Скобелев В. Г. О статистически приводимых автоматах. Изв. вузов. Матем., № 2. — 1989. — С. 6-10.
165. Барашко А.С., Черевко Н.В. Некоторые способы оценки длины случайного теста // в сб.: Теория и моделирование управляющих систем. — Киев : Наукова думка, 1989. — С. 10-15.
166. Белозеров А.А., Мельников С.Ю., Пересыпкин В.А. Технологические аспекты построения системы сбора корпусов текстов // Материалы 4-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» (СКТ-2016). — Т. 2. — Ростов-на-Дону : Издательство Южного федерального университета, 2016. — С. 112-115.
167. Белозеров А.А., Мельников С.Ю., Пересыпкин В.А. Технологии очистки текстовых корпусов для разработки моделей языка // Материалы 4-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» (СКТ-2016). — Т. 2. - Ростов-на-Дону : Издательство Южного федерального университета, 2016. — С. 115-119.
168. Белозеров А.А., Вахлаков Д.В., Мельников С.Ю. Подходы к коррекции искаженных текстов // Материалы 5-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» СКТ-2018. — Т. 1. — Ростов-на-Дону : Издательство Южного федерального университета, 2018. — C. 66-70.
169. Белозеров А.А., Вахлаков Д.В., Мельников С.Ю., Пересыпкин В.А., Сидоров Е.С. Технологические аспекты построения системы сбора и предобработки корпусов новостных текстов для создания моделей языка // Известия ЮФУ. Технические науки, № 12 (185), 2016. — С. 29-42.
170. Белозеров А.А., Вахлаков Д.В., Мельников С.Ю., Пересыпкин В.А., Скавинская Д.В. О реализации эволюционных методов дискретной оптимизации для коррекции искаженных текстов // Материалы 10-й Всероссийской мультиконференции по проблемам управления МКПУ-2017. — т. 1. — Ростов-на-Дону : Издательство Южного федерального университета. — C. 26-30.
171. Белозеров А.А., Вахлаков Д.В., Мельников С.Ю., Пересыпкин В.А., Скавинская Д.В. Использование эволюционных методов дискретной оптимизации для коррекции искаженных текстов // Вестник компьютерных и информационных технологий, № 12. — 2018. — C. 3-10.
172. Белозеров А.А., Вахлаков Д.В., Мельников С.Ю., Пересыпкин В.А. Подходы к автоматической коррекции искаженных текстов // Материалы 5-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» СКТ-2018. — Т. 1. — Ростов-на-Дону : Издательство Южного федерального университета, 2018. — C. 66-70.
173. Беликов В.И. Жестовые системы и коммуникация (обзор) // Семиотика и информатика. — Вып. 20. — М., 1983. — С. 127-148.
174. Бирин Д.А., Мельников С.Ю., Пересыпкин В.А. Об эффективности средств коррекции искаженных текстов // Материалы 5-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии» СКТ-2018. — Т. 1 — Ростов-на-Дону : Издательство Южного федерального университета, 2018. — C. 71-75.
175. Бирин Д.А., Мельников С.Ю., Пересыпкин В.А. Подходы к объективизации экспертных оценок качества коррекции искаженных текстов // Материалы 1 2-й мультиконференции по проблемам управления МКПУ-2019. — Т. 1. — Ростов-на-Дону : Издательство Южного федерального университета. — C. 36-38.
176. Бирин Д.А., Мельников С.Ю., Пересыпкин В.А., Писарев И.А., Цопкало Н.Н. Об эффективности средств коррекции искаженных текстов в зависимости от характера искажений // Известия ЮФУ. Технические науки, № 8, 2018. — С. 104-114.
177. Брославский М.В., Мельников С.Ю. Сравнение эффективности классификаторов в задаче текстонезависимой идентификации автора русскоязычного рукописного текста // Обозрение прикладной и промышленной математики, т. 25, вып. 3, 2018. — C. 234-235.
178. Бурделев А. В., Никонов В. Г., Лапиков И. И. Распознавание параметров узла защиты информации, реализованного пороговой k-значной функцией // Тр. СПИИРАН, т. 46, 2016. — С. 108-127.
179. Бухараев Р.Г. К задаче минимизации входа автомата, генерирующего заданную однородную цепь Маркова // Учен. зап. Казан. ун-та, т. 129, книга 4. — 1969. — С. 3-11.
180. Бухараев Р.Г. Основы теории вероятностных автоматов. — М. : Наука, 1985. — 288 с.
181. Варфоломеев А. А., Жуков А. Е., Пудовкина М. А. Поточные криптосистемы. Основные свойства и методы анализа стойкости. — М. : ПАИМС, 2000. — 272 с.
182. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М. : ДИАЛОГ-МИФИ, 2002. — 384 с.
183. Вахлаков Д.В., Мельников С.Ю., Пересыпкин В.А. Совместное использование различных моделей языка в задаче коррекции искаженных текстов // Материалы 1 2-й мультиконференции по проблемам управления МКПУ-2019. — Т. 1. — Ростов-на-Дону : Издательство Южного федерального университета, 2019. — C. 41-44.
184. Вахлаков Д.В., Мельников С.Ю., Пересыпкин В.А. Многоэтапный метод автоматической коррекции искаженных текстов // Известия ЮФУ. Технические науки, № 7, 2020. — C. 35-45.
185. Вахлаков Д.В., Мельников С.Ю., Пересыпкин В.А. Многоэтапный алгоритм коррекции искаженных текстов. Аспекты точности и вычислительной трудоемкости //
Суперкомпьютерные технологии : сборник трудов молодых ученых. — Ростов-на-Дону — Таганрог : Издательство ЮФУ, 2020. — С. 39-42.
186. Гантмахер Ф.Р. Теория матриц. — 5-е изд. — М., ФИЗМАТЛИТ, 2004. — 560 с.
187. Генератор текста на основе цепей Маркова, http://www.manhunter.ru/webmaster/358_generator_teksta_na_osnove_cepey_markova.html.
188. Германович А.В., Мельников С.Ю., Хвостенко В.М. О выборе множества слов, характеризующих авторский стиль арабского текста // Обозрение прикладной и промышленной математики, т. 24, вып. 4. — 2017. — С. 324-325.
189. Германович А.В., Мельников С.Ю., Пересыпкин В.А., Сидоров Е.С., Цопкало Н.Н. Информационные измерения языка. Программная система оценки читаемости искаженных текстов // Известия ЮФУ. Технические науки, № 8. — 2019. — C. 6-18.
190. Гизунов С.А., Носов В.А. О классификации всех булевых функций 4-х переменных по классам Шефера // Обозрение прикладной и промышленной математики, т. 2, № 3. — 1995. — С. 440-467.
191. Глибовец Н.Н., Заднепровский К.Г. Об одном подходе к решению задачи нахождения всех контуров в ориентированных графах // Модели и системы обраб. информ. (Киев), № 9. — 1990. — С. 87-93.
192. Глухов М. М., Елизаров В. П., Нечаев А.А. Алгебра. — М. : Гелиос АРВ, 2003. — Т. 2. — 414 с.
193. Голембиовский Д.Ю. Диагностика цифровых устройств. Микропрограммное и вероятностное тестирование // Саратов. Политехн. ин-т, 1993. — 27 с.
194. Гребешкова Г.Ю., Сперанский Д.В. О минимизации длины псевдослучайного теста для цифровых устройств // Автоматика и вычислительная техника, № 5, 1990. — С. 90-94.
195. Гречников Е.А., Гусев Г.Г., Кустарев А.А., Райгородский А.М. Поиск неестественных текстов // Труды XI всероссийской конференции «Цифровые библиотеки: продвинутые методы и технологии, цифровые коллекции». — RCDL'2009, Петрозаводск, 2009. — С. 306-308.
196. Гришкин А.С. Генераторы псевдослучайных символов на регистрах сдвига с внутренними сумматорами по модулю два при использовании инверсных выходов // Дис. ... к.т.н., 05.13.05 — Элементы и устройства вычислительной техники и систем управления, Казань, КГТУ, 2006. — 142 с.
197. Грушо А.А., Грушо Н.А., Тимонина Е.Е. Включение новых запретов в случайные последовательности // Информ. и ее примен., т. 8(4), 2014. — С.46-52.
198. Дуб Дж.Л. Вероятностные процессы. — М. : Изд. иностр. лит., 1956. — 606 с.
199. Духин А.А. Теория информации. — М. : Гелиос АРВ, 2007. — 248 с.
200. Ермилов А.В. Распознавание языка искаженного текста методом опорных векторов // Вестник РУДН. Серия Математика, Информатика, Физика. Т. 2. — 2012. — С. 126-130.
201. Зыков А.П. Метод сглаживания вероятностей n-грамм на основе моделирования математического ожидания их встречаемости // Труды СПИИРАН. Вып. 19. — 2011. — C. 146158.
202. Ибраев Я.И. Надзнаковость языка (к проблеме отношения семиотики и лингвистики) // Вопросы языкознания, № 1. — 1981. — С. 1-25.
203. Иванов В.А. Случайные последовательности конечного ранга. — М. : МИЭМ, 1992. — 90 с.
204. Икрамов Х.Д. Унитарные конгруэнции и теоремы о псевдоперестановочных матрицах // Докл. РАН, т.413(6) . — 2007. — С. 727-729.
205. Камловский О.В. Оценки частот появления элементов в линейных рекуррентных последовательностях над кольцами Галуа / О.В. Камловский, А.С. Кузьмин // Фундамент. и прикл. матем., т. 6, вып.4. — 2000. — С. 1083-1094.
206. Кац М. Статистическая независимость в теории вероятностей, анализе и теории чисел. М. : Изд-во иностр. лит, 1962. — 156 с.
207. Кемени Дж., Снелл Дж. Конечные цепи Маркова. — М. : Наука, 1970. — 272 с.
208. Кнорозов Ю.В. Письменность древних майя: опыт расшифровки // Советская этнография, № 1, 1955. — С. 94-115.
209. Кнут Д.Э. Искусство программирования. В 3-х т. [Текст] : учебное пособие. Т. 2. Получисленные алгоритмы / Пер. с англ. — 3-е изд. — М. : Издательский дом «ВИЛЬЯМС», 2001. — 832 с.
210. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. — М. : Наука, 1989. — 624 с.
211. Колодзей А.В. Контрольные множества ориентированных графов // Обозрение прикладной и промышленной математики, т. 22, вып. 1, 2015.
212. Колпаков Р.М. Дискретные преобразования вероятностных распределений // Современные проблемы математики и механики. Том III. Математика. Вып. 3. Дискр. мат. — М. : Изд-во МГУ, 2009. — С. 35-50.
213. Королюк В.С., Портенко Н.И., Скороход А.В., Турбин А.Ф. Справочник по теории вероятностей и математической статистике. — М. : Наука, 1985. — 640 с.
214. Котов М.А., Леднов Д.А., Мельников С.Ю., Федюкин М.В., Широкова А.М. Система определения параметров линейчатых спектров вокализованных звуков. Патент на полезную модель RUS 78470, 11.06.2008.
215. Котов М.А., Леднов Д.А., Мельников С.Ю., Федюкин М.В., Широкова А.М. Способ определения параметров линейчатых спектров вокализованных звуков и система для его реализации. Патент на изобретение № 2364957. - М. : Российское агентство по патентам и товарным знакам, 20.08.2009.
216. Кратко М.И., Строк В.В. Последовательности де Брейна с ограничениями // В кн. : Вопросы киберн. Комбинаторный анализ и теория графов. М. : Изд. АН СССР, 1980. — С. 8084.
217. Круглов И.А. О вполне неразложимых неотрицательных матрицах и условии А.Н. Колмогорова // Фундамент. и прикл. матем., т. 20(1), 2015. — С. 167-172.
218. Круглова С.И., Мельников С.Ю., Сидоров Е.С. Способ совместного выбора параметров метода импосторов в открытой задаче идентификации авторства текста (русский язык) // Обозрение прикладной и промышленной математики, т. 26, вып. 2, 2019. — С. 272-275.
219. Крук Е.А. Надежные методы передачи, хранения и обработки информации: учебное пособие. — Л. : ЛИАП, 1989, 46 с.
220. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. — М. : Наука, Гл. ред. физ.-мат. лит., 1985. — 320 с.
221. Кудрявцев В.Б., Грунский И.С., Козловский В.А. Восстановление автоматов по фрагментам поведения // Дискрет.матем., 2009, т. 21, вып. 2. — С. 3-42.
222. Кулай А.Ю., Леднов Д.А., Мельников С.Ю. О статистических методах идентификации языка искаженных текстовых и речевых сообщений // Известия ЮФУ. Технические науки, № 8, 2008. — С. 177-183.
223. Кулай А.Ю., Леднов Д.М., Мельников С.Ю. Методы идентификации языка речевых и искаженных текстовых сообщений // Материалы Х Международной научно-практической конференции «Информационная безопасность». Ч. 2. — Таганрог : Изд-во ТТИ ЮФУ, 2008. — C.100-102.
224. Кулай А.Ю., Мельников С.Ю. Сравнение нескольких подходов к распознаванию языков искаженных текстов // Труды второй международной конференции «Системный анализ и информационные технологии» (САИТ-2007), (Обнинск, Россия), 10-14 сентября 2007 г. М. : Издательство ЛКИ, 2007, т. 1. — С. 218-220.
225. Кулай А.Ю., Мельников С.Ю. О точности идентификации языка искаженного текста в зависимости от степени искажения // Концептуальный спектр изысканий в современном речеведении (Вестн. Моск. гос. лингвист. ун-та, вып. 575, сер. Языкознание). — М. : ИПК МГЛУ «Рема», 2009. — С. 200-209.
226. Кулай А.Ю., Мельников С. Ю. Об эффективности идентификации языка искаженных текстов в зависимости от степени искажения // Третья Международная конференция
«Системный анализ и информационные технологии» САИТ-2009 (14-18 сентября 2009 г., Звенигород, Россия): Труды конференции. — М., 2009. — С. 188-190.
227. Кулай А.Ю., Мельников С.Ю. О моделировании результатов работы фонетического распознавателя с помощью вероятностного автомата, обрабатывающего тексты // Обозрение прикладной и промышленной математики, т. 18, вып. 2. — 2011. — С. 291-292.
228. Кулай А.Ю., Мельников С.Ю. Технологические аспекты построения системы идентификации языка текстовых документов // Сб. трудов XIV Международной конференции «Речь и компьютер - 2011» (SPEC0M'2011) (Казань, 27-30 сентября 2011 г.). — М., 2011. — C. 350-352.
229. Кулямин В.В. Комбинаторика слов и построение тестовых последовательностей // Труды института системного программирования РАН, т. 8, № 1. — 2004. — С. 25-40.
230. Курант Р., Робинс Г. Что такое математика? — 3-е изд., испр. и доп. — М. : МЦНМО, 2001. — 568 с.
231. Кушик Н.Г. Методы синтеза установочных и различающих экспериментов с недетерминированными автоматами : дис. ... к.ф.-м.н., 05.13.01 — Системный анализ, управление, обработка информации. — Томск, 2013. — 137 с.
232. Леонтьев Н.А., Слепцов И.А. Идентификация текстового документа с помощью триграмм на материалах якутского языка // Вестник Северо-Восточного федерального университета им. М.К. Аммосова, т. 4 (48) . — 2015. — С. 45-50.
233. Ли Д., Препарата Ф. Вычислительная геометрия. Обзор // В кн. «Кибернетический сборник», вып. 24, М. : Мир, 1987. — С. 5-96.
234. Логачев О.А., Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии. — М. : МЦНМО, 2004. — 470 с.
235. Максимов А.В., Мельников С.Ю., Чавчавадзе Н.М. Тенденции развития методов автоматической идентификации языка речевых и текстовых сообщений // Обозрение прикладной и промышленной математики, т. 16, в. 2. — 2009. — С. 365-367.
236. Максимов А.В., Мельников С.Ю., Чавчавадзе Н.М., Федюкин М.В. Развитие систем автоматической текстонезависимой идентификации дикторов // Обозрение прикладной и промышленной математики, т. 16, в. 6. — 2009. — С. 1091-1092.
237. Максимов А.В., Мельников С.Ю., Чавчавадзе Н.М., Федюкин М.В. О применении методов адаптации вероятностных моделей языка для повышения точности работы систем распознавания речи // Обозрение прикладной и промышленной математики, т. 17, вып. 6. — 2010. — С. 906-907.
238. Максимовский А.Ю., Мельников С.Ю. О планарности одного подкласса обобщенных графов де Брейна // Обозрение прикладной и промышленной математики, т. 18, вып. 4. — 2011.
— С. 647-648.
239. Максимовский А.Ю., Мельников С.Ю. О числе обобщенных в смысле Imase и Itoh регистров сдвига, устанавливаемых постоянным входом в фиксированное состояние // Обозрение прикладной и промышленной математики, т. 22, вып. 5. — 2015.
240. Максимовский А.Ю., Мельников С.Ю. Спектральные и комбинаторные свойства редуцированных графов де Брейна // Вопросы кибербезопасности, № 4(28). — 2018. — C. 7076.
241. Малышев Ф.М., Тараканов В.Е. Обобщенные графы де Брейна // Матем. заметки, т. 62, № 4. — 1997. — С. 540-548.
242. Марков А.А. Пример статистического исследования над текстом «Евгения Онегина», иллюстрирующий связь испытаний в цепь // Известия Имп. Акад. наук, серия VI, т. X, № 3. — 1913. — С. 153-162.
243. Маркус М., Минк Х. Обзор по теории матриц и матричных неравенств. М. : Наука, 1972.
— 232 с.
244. Мельников А.К., Ронжин А.Ф. Обобщенный статистический метод анализа текстов, основанный на расчете распределений вероятностей значений статистик // Информ. и ее примен., т. 10(4). — 2016. — С. 89-95.
245. Мельников С.Ю. Спектры неориентированных графов де Брейна и верхняя граница числа независимости для таких графов // Дискр. матем., том 7, вып.4, 1995, С.140-144.
246. Мельников С.Ю. Многогранники, характеризующие статистические свойства конечных автоматов // Труды по дискретной математике, том 7. — Издательство физико-математической литературы, 2003. — С. 126-137.
247. Мельников С.Ю. О переработке конечными автоматами чезаровских последовательностей // Вестн. Моск. гос. ун-та леса Лесной вестник, № 1(32). — 2004. — С.169-174.
248. Мельников С.Ю. Регистры сдвига с чезаровским входом // Вестн. Моск. гос. ун-та леса Лесной вестник, № 4(35). — 2004. — С. 200-202.
249. Мельников С.Ю. О геометрической характеристике статистических свойств конечных сильносвязных автоматов Мили // Обозрение прикладной и промышленной математики, т. 11, вып. 4. — 2004. — С. 880-881.
250. Мельников С.Ю. Геометрический подход к задаче идентификации конечного автомата по статистическим свойствам его входной и выходной последовательностей // Первая Международная конференция «Системный анализ и информационные технологии» САИТ-2005
(12-16 сентября 2005 г., Переславль-Залесский, Россия). (Серия: Труды Института системного анализа РАН) Тр. конф. в 2 т., т.2. — М. : КомКнига, 2005.
251. Мельников С.Ю. Спектр неориентированных степеней двоичного графа де Брейна // Обозрение прикладной и промышленной математики, т. 13, вып. 4. — 2006. — С. 682-683.
252. Мельников С.Ю. О восстановлении функции выходов автономного вероятностного автомата Мура по значениям вероятностей биграмм в его выходной последовательности // Обозрение прикладной и промышленной математики, т. 13, вып. 4. — 2006. — С. 682.
253. Мельников С.Ю. Об использовании спектров графов автоматов в задаче определения функции выходов по вероятностям биграмм в выходной последовательности // Вестн. Моск. гос. ун-та леса Лесной вестник, № 2(51). — 2007. — С. 153-158.
254. Мельников С.Ю. О классе двоичных функций, сохраняющих значковые статистические свойства последовательностей при преобразовании сдвигового типа // Обозрение прикладной и промышленной математики, т. 14, вып. 6. — 2007. — С. 1123-1124.
255. Мельников С.Ю. О статистических характеристиках обработки двоичных последовательностей регистром сдвига с последовательным суммированием // Обозрение прикладной и промышленной математики, т. 16, в. 4. — 2009. — С. 682-683.
256. Мельников С.Ю. Двоичные обобщенные неавтономные регистры сдвига не наследуют чезаровские свойства входной последовательности // Обозрение прикладной и промышленной математики, т. 17, вып. 6. — 2010. — С. 910-911.
257. Мельников С.Ю. О возможности использования вероятностной функции конечного автомата Мура в задаче определения функции выходов // Обозрение прикладной и промышленной математики, т. 17, вып. 6. — 2010. — С. 882-883.
258. Мельников С.Ю. Многоугольники, характеризующие статистические свойства булевых функций в схеме регистра сдвига // Вестник Российского государственного гуманитарного университета, № 12. — 2010. — С. 137-159.
259. Мельников С.Ю. О статистической эквивалентности двоичных функций в схеме регистра сдвига с бернуллиевским и марковским входом // Обозрение прикладной и промышленной математики, т. 18, вып. 2. — 2011. — С. 305-306.
260. Мельников С.Ю. О задаче определения функции выходов автомата со случайным входом по статистике встречаемости слова в выходной последовательности // Докл. Томск. унта сист. упр. и радиоэл. (ТУСУР), серия «Управление, вычислительная техника и информатика», № 1 (23). — 2011. — С. 107-123.
261. Мельников С.Ю. Об идентификации регистров сдвига с троичным входом по значковым статистическим свойствам входной и выходной последовательностей // Обозрение прикладной и промышленной математики, т. 19, вып. 3, 2012, С. 412-413.
262. Мельников С.Ю. Определение языка текста как задача идентификации вероятностного автомата // Обозрение прикладной и промышленной математики, т. 20, вып. 5. — 2013.
263. Мельников С.Ю. Идентификация конечных автоматов на основе метода многогранников. — М. — Ижевск : Ин-т компьютерных иссл., 2013. — 136 с. ISBN 978-5-43440108-1.
264. Мельников С.Ю. Верификация по голосу: надежно ли? Впечатления, наблюдения и размышления участника конференции Interspeech2013 // BIS Journal — Информационная безопасность банков №1(12). — 2014. — С. 36-39.
265. Мельников С.Ю. Неавтономные двоичные регистры сдвига, сохраняющие значковые статистические свойства входной последовательности // Докл. Томск. ун-та сист. упр. и радиоэл. (ТУСУР), № 2(36). — 2015. — С. 86-99.
266. Мельников C. Ю. О случайных блужданиях на обобщенных в смысле Imase и Ito графах де Брейна // Материалы XXI научно-практической конференции «Комплексная защита информации» 17-19 мая 2016 года, Смоленск. — 2016. — C. 212-213.
267. Мельников С.Ю. Статистические свойства неавтономных обобщенных двоичных регистров сдвига // Докл. Томск. ун-та сист. упр. и радиоэл. (ТУСУР), т. 20, № 1. — 2017. — С. 93-95.
268. Мельников С.Ю. Регистры сдвига с последовательным суммированием не сохраняют статистические свойства входной последовательности // Обозрение прикладной и промышленной математики, т. 24, вып. 5. — 2017.
269. Мельников С.Ю. Подход к оценке информативности метода многогранников в задаче верификации автомата по статистическим свойствам входной и выходной последовательностей // Обозрение прикладной и промышленной математики, т.27, вып. 2. — 2020. — С. 154-157.
270. Свидетельство о государственной регистрации программы для ЭВМ № 2017615913. Анализ статистических свойств неавтономных двоичных регистров сдвига и обобщенных регистров сдвига. Правообладатель и автор: Мельников С.Ю. Заявка № 2017613213. Дата поступления 30 марта 2017 г. Дата государственной регистрации в Реестре программ для ЭВМ 26 мая 2017 г.
271. Мельников С.Ю., Мельников Н.С. О классе двоичных функций, сохраняющих значковые статистические свойства последовательностей при преобразовании обобщенно-сдвигового типа // Обозрение прикладной и промышленной математики, т. 16, в. 2. — 2009. — С. 369.
272. Мельников С.Ю., Пересыпкин В.А. Тенденции развития языковых моделей в задачах распознавания, аспекты точности и вычислительной трудоемкости // Материалы 8-й Всероссийской мультиконференции по проблемам управления МКПУ-2015. —С. Дивноморское. — Т. 1. — С. 85-87.
273. Мельников С.Ю., Пересыпкин В.А. О применении вероятностных моделей языка для обнаружения ошибок в искаженных текстах // Вестник компьютерных и информационных технологий, № 5, 2016, С.29 - 34.
274. Мельников С.Ю., Пересыпкин В.А., Скавинская Д.В. О подходе к коррекции искаженных текстов на основе эволюционных методов дискретной оптимизации // Материалы 9-й Всероссийской мультиконференции по проблемам управления МКПУ-2017. — Ростов-на-Дону : Издательство Южного федерального университета, т. 1. — С. 73-78.
275. Мельников С.Ю., Самуйлов К.Е. Распознавание функции выходов автомата со случайным входом по значковым свойствам выходной последовательности // Материалы XXI Международной научной конференции БССК-2018, РУДН, 2018. — С. 293-300.
276. Мельников С. Ю., Самуйлов К. Е. Вероятностные функции и статистическая эквивалентность двоичных регистров сдвига со случайным марковским входом // Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем : материалы Всероссийской конференции с международным участием. Москва, РУДН, 13-17 апреля 2020 г. — Москва : РУДН, 2020, С. 49-54.
277. Мельников С. Ю., Самуйлов К. Е. О распознавании функции выходов регистра сдвига со случайным входом для марковской модели входной последовательности // Информационно-телекоммуникационные технологии и математическое моделирование высокотехнологичных систем : материалы Всероссийской конференции с международным участием. Москва, РУДН, 13-17 апреля 2020 г. — Москва : РУДН, 2020. — С. 55-58.
278. Мельников С.Ю., Самуйлов К.Е. Статистические свойства двоичных неавтономных регистров сдвига с внутренним суммированием // Информатика и ее применение. № 2, 2020, С. 80-85.
279. Мельников С.Ю., Федюкин М.В. К вопросу об информационной защищенности систем обработки и анализа речевых и текстовых сообщений от пассивных атак // Обозрение прикладной и промышленной математики, т. 18, вып. 4. — 2011. — С. 651-652.
280. Мори Т. Случайные блуждания на графах де Брейна // Теория вероятностей и ее применения, т. 37, вып. 1. — 1992. — С. 194-197.
281. Мясоедова М.А., Мясоедова З.П. Межъязыковые особенности жестовых языков (на материале жестов в знаковой форме) // Современные информационные технологии и ИТ-образование, т. 15, № 1. — 2019. — С. 172-181.
282. Нетыкшо В.Б. Восстановление параметров дискретных устройств, основанное на переоценке вероятностей с использованием действительных пороговых соотношений : диссертация ... кандидата технических наук : 05.13.11. — Москва, 2003. — 148 с.
283. Никонов В.Г. Классификация минимальных базисных представлений всех булевых функций от четырех переменных // Обозрение прикладной и промышленной математики, т.1, вып. 3. — 1994. — С. 458-545.
284. Никонов В.Г., Никонов Н.В. Запреты к-значных функций и их связь с проблемой разрешимости систем уравнений специального вида // Вестник РУДН. Прикладная и компьютерная математика, т. 2, № 1. — 2003. — С. 79-93.
285. Ню В. О числе внешней устойчивости обобщенных графов де Брейна // Сиб. журн. исслед. операций, том 1, № 2. — 1994. — С. 61-66.
286. Ню В. Число внутренней устойчивости графа перекрытий двоичных слов длины п // В кн.: Тез. докл. 7 Всесоюзной конф. по пробл. теоретич. киберн. — Иркутск, 1985. — С. 155.
287. Ню В. Число независимости графа де Брейна // - В кн.: Методы дискретного анализа в синтезе управляющих систем № 44. — Новосибирск, 1986. — С. 58-68.
288. Ожегов С.И., Шведова Н. Ю. Толковый словарь русского языка, 22-е издание. — 1992.
289. Орлов Ю.Н., Шилин С.А. Статистическое распознавание языка текста по частоте буквосочетаний // Препринты ИПМ им. М.В. Келдыша, 2017, № 032, 21 с.
290. Павлов А.С., Добров Б.В. Метод обнаружения массово порожденных неестественных текстов на основе анализа тематической структуры // Вычислительные методы и программирование, т. 12. — 2011. — С. 58-72.
291. Павлов А.С., Добров Б.В. Методы обнаружения поискового спама, порожденного с помощью цепей Маркова // Труды XI всероссийской конференции «Цифровые библиотеки: продвинутые методы и технологии, цифровые коллекции» . — RCDL'2009, Петрозаводск, 2009. — С. 311-317.
292. Пархоменко Д.В. Гистограммная функция автомата и ее приложения // Дис. ... к.ф.-м.н. 01.01.09 — Дискретная математика и математическая кибернетика, М. : МГУ, 2015. — 86 с.
293. Песошин В.А., Кузнецов В.М., Гумиров А.И. Генераторы псевдослучайных последовательностей немаксимальной длины на основе регистра с внутренними сумматорами по модулю два (часть 1) // Вестник Чувашского университета № 1, 2017. — С. 263-272.
294. Петрухнова Г.В. Оценка длины случайной последовательности для операции воспроизведения информации в контрольном испытании // Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях: Сб. тр. / под ред. Кравца О.Я. — Воронеж : Изд. Научная книга, вып. 9, 2004. — С. 303-305.
295. Пиперски А. Конструирование языков: от эсперанто до дотракийского. -М. : Альпина нон-фикшн, 2017. — 224 с.
296. Погорелов Б.А., Сачков В.Н. Словарь криптографических терминов. — М. : МЦНМО, 2006. — 91 с.
297. Поддубный В.В., Шевелев О.Г. Образует ли последовательность символов текста простую цепь Маркова? // Вестник Томского гос. ун-та, № 16. — 2006. — С. 129-136.
298. Потапова Р.К., Потапов В.В., Хитина М.В. Определение темы текста, воспринятого в затрудненных условиях (экспериментальное исследование) // Proceedings of the 14th International Conference "Speech and computer" (SPECOM 2011), Moscow-Kazan, 2011. — C. 168-172.
299. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М. : Мир, 1989. — 478 с.
300. Риордан Дж. Комбинаторные тождества. — М. : Наука, 1982. — 256 с.
301. Рожков М.И. Алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм : дис. ... д.т.н., 05.13.19 — Методы и системы защиты информации. Информационная безопасность. — М. : МГИЭМ, 2012. — 265 с.
302. Романов А.С., Шелупанов А.А., Мещеряков Р.В. Разработка и исследование математических моделей, методик и программных средств информационных процессов при идентификации автора текста // Томск : В-Спектр, 2011. — 188 с.
303. Рябинин А. В. Стохастические функции конечных автоматов // Алгебра, логика и теория чисел, 7 темат. конф. мех.-мат. фак. МГУ, фев.-март 1985, М., 1986. — С. 77-80.
304. Сарымсаков Т.А. Основы теории процессов Маркова. — М. : Гос. изд. техн.-теор. лит., 1954. — 208 с.
305. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М. : Наука, 1982. — 384 с.
306. Сачков В.Н. Курс комбинаторного анализа. — Ижевск : НИЦ «Регулярная и хаотическая динамика», 2013. — 336 с.
307. Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. — М. : изд-во ТВП, 2000. — 448 с.
308. Свами М., Тхуласираман К. Графы, сети и алгоритмы. - М. : Мир, 1984. — 455 с.
309. Севастьянов Б.А. Условное распределение выхода автоматов без памяти при заданных характеристиках входа // Дискретн. матем., т. 6., вып. 1, 1994. — С. 34-39.
310. Севастьянов Б.А. Исследование вероятностной зависимости выхода автомата от некоторых характеристик входа // В сб.: Труды по дискретной математике. Т. 5 . — М. : ФИЗМАТЛИТ, 2002. — С. 219-226.
311. Северин Н.В. Методы нечеткого поиска в системах контроля нецелевого контента // Вюник Схщноукрашського нацюнального ушверситету iм.В.Даля, № 8 (179), Ч. 2, 2012. — C. 199-205.
312. Северин Н.В. Применение методов теории подобия конечных последовательностей для идентификации сообщений в системах телекоммуникаций // Науковi пращ ОНАЗ iм. О.С. Попова, № 1, 2014. — С. 116-123.
313. Сперанский Д.В., Черевко Н.В. Об оптимизации распределения вероятностей входных сигналов при случайном тестировании дискретных устройств // Электронное моделирование, № 2. — 1992. — С. 46-54.
314. Строк В.В. Спектры графов некоторых классов последовательностей // В кн.: Всесоюз. алгебраич. симпоз. Тез. докл. В 2-х ч. Ч. 2. — Гомель : Изд. АН СССР — АН БССР, 1975. — С. 452.
315. Строк В.В. Циркулянтные матрицы и спектры графов де Брейна // Укр. мат. журн., т. 44, № 11, 1992. — С. 1571-1579.
316. Сумароков С.Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств // Обозрение прикл. и пром. мат., т. 1, вып. 1, 1994. — С. 33-55.
317. Тараканов В.Е. О группах автоморфизмов обобщенных графов де Брейна // Труды по дискр. матем., т. 5., 2002. — С. 235-240.
318. Твердохлебов В.А. Геометрические образы конечных детерминированных автоматов // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика, том 5, выпуск 1-2. — 2005. — С. 141-153.
319. Твердохлебов В.А. Представление автоматных отображений геометрическими структурами : моногр. / В.А. Твердохлебов, А.С. Епифанов. — Саратов : ООО Издательский Центр «Наука», 2013. — 204 с.
320. Тимонина Е.Е. Анализ угроз скрытых каналов и методы построения гарантированно защищенных распределенных автоматизированных систем : дис. ... д.т.н. 05.13.17 — Теоретические основы информатики, Москва, РГГУ, 2004. — 204 с.
321. Тяпаев Л.Б. Решение некоторых задач для конечных автоматов на основе анализа их поведения // Изв. Сарат. ун-та. Нов. сер. Т. 6. Сер. Математика. Механика. Информатика, вып. 2, 2006. — С. 121-133.
322. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. — Т. 2. — М. : Наука, 1969. — 800 с.
323. Харари Ф. Теория графов. — М. : Мир, 1973. — 300 с.
324. Холл М. Комбинаторика. — М. : Мир, 1970. — 424 с.
325. Хорн Р., Джонсон Ч. Матричный анализ. — М. : Мир, 1989. — 655 с.
326. Хохлов В.И. Точные формулы для вторых моментов условных преобладаний по Севастьянову // Обозрение прикладной и промышленной математики, т. 10, вып. 3. — 2003. — С. 582-589.
327. Хренников А.Ю. Интерпретация вероятностей и их р-адические расширения // Теория вероятн. и ее примен., том 46, вып. 2. — 2001. — С. 311-325.
328. Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория и применение // Киев : Наукова думка, 1984. — 384 с.
329. Черемушкин А. В. Методы аффинной и линейной классификации двоичных функций // Тр. по дискр. матем., вып. 4. — 2001. — С. 273-314.
330. Шалимов И.А., Бессонов М.А. Обзор методов автоматической идентификации языка аудиосообщения // Труды НИИР, № 3, 2011. — С. 43-47.
331. Шалимов И.А., Бессонов М.А., Костенко А.И., Босомыкин Д.В. О повышении достоверности определения языка аудиосообщения на основе просодической классификации // Труды НИИР, № 4, 2014. — С. 2-7.
332. Шеннон К. Предсказание и энтропия английского печатного текста // Сб. тр. «Работы по теории информации и кибернетике». — М. : Иностр. литература, 1963. — С. 669-686.
333. Шеришева Е.В. О числе конечных автоматов, устанавливаемых постоянным входом в фиксированное состояние // Дискретная математика, т. 6, вып. 4, 1994. — С. 80-86.
334. Шкоропат Е.А. Возможности диагностирования состояния алкогольного опьянения исполнителя рукописи по признакам письма // Судебная экспертиза, № 4, 2007. — С. 91 -100.
335. Шумская А.О. Метод определения искусственных текстов на основе расчета меры принадлежности к инвариантам // Труды СПИИРАН, вып. 6(49), 2016. — С. 104-121.
336. Якобс К. Машинно-порожденные 0-1 последовательности, в кн.: Машины Тьюринга и рекурсивные функции. — М. : Мир, 1972. — С. 216-247.
337. Яшунский А.Д. Преобразования бернуллиевских распределений булевыми функциями из замкнутых классов // Препринты ИПМ им. М.В. Келдыша, № 38, 2016. — 23 с.
ПРИЛОЖЕНИЕ А
ДОКУМЕНТЫ, ПОДТВЕРЖДАЮЩИЕ ВНЕДРЕНИЕ ОСНОВНЫХ РЕЗУЛЬТАТОВ
ДИССЕРТАЦИОННОЙ РАБОТЫ
Экз. №
УТВЕРЖДАЮ
Генеральный директор
1-математических наук
а
Общество с ограниченной
ответственностью «ЛИНГВИСТИЧЕСКИЕ И ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ» (ООО «Линфо»)
127018, г. Москва, ул. Образцова, д.38, стр. тел./факс +7(495) 249-90-53 e-mail: info@linfotech.ru
№15-21 от 02.03.2021 г.
АКТ
О внедрении результатов диссертационной работы Мельникова Сергея Юрьевича "Методы распознавания и идентификации конечных автоматов по статистическим характеристикам выходных и входных последовательностей»
Комиссия в составе: председателя комиссии: членов комиссии:
научного консультанта, к.ф.-м.н., Ульяненко В.П., начальника отдела разработки программного обеспечения и электронного обучения Пичкура К.Б.,
Ведущего программиста отдела разработки программного обеспечения и электронного обучения Скопцовой Е.В.
составила настоящий акт о том, что нижеперечисленные научные результаты диссертационной работы Мельникова Сергея Юрьевича «Методы распознавания и идентификации конечных автоматов по статистическим характеристикам выходных и входных последовательностей», представленной на соискание научной степени доктора физико-математических наук, использованы для разработки программно-аппаратного комплекса при выполнении договора № 9/184.17 от 30.08.2017 с ФГУП «РНИИРС»:
1. Разработан метод распознавания функции выходов конечного вероятностного автомата по значениям вероятностей биграмм в его выходной последовательности на основе решения системы квадратичных уравнений, где вектором неизвестных является вектор табличного задания функции выходов, а количество уравнений — это количество известных значений вероятностей биграмм.
2. Введены и исследованы многогранники автоматов, описывающие совместные статистические свойства входной и выходной последовательностей. Получено представление этих многогранников как выпуклой оболочки множества точек в действительном кубе подходящей размерности. Получены оценки трудоемкости
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.