Свойства отображений, непредставимых частными классами конечных автоматов

• Автор: Батраева, Инна Александровна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Саратов
• Количество страниц: 90 с.

СОДЕРЖ АНИЕ
Введение
1. Свойства отображений, непредставимых специальными классами конечных детерминированных автоматов

1.1. Основные понятия и определения

1.2. Построение иерархии классов конечных детерминированных автоматов.

1.3. Необходимое и достаточное условие отделимости классов конечных автоматов

1.4. Виды нереализуемых отображений

1.4.1. Нереализуемые связи для однородных входных последовательностей

1.4.2. Нереализуемые связи между периодическими и квазипериодическими входными последовательностями и выходными последовательностями

1.4.3. Использование универсальных тестов

2. Свойства геометрических образов автоматов и классов автоматов
2.1. Словарная геометрия и построение геометрических образов автоматов
2.2. Преобразование образа при изменении порядка в пространстве
2.3. Закон изменения мощностных характеристик образа при переходе от клетке к клетке
2.4. Геометрическое условие неавтоматности
3. Свойства линейных последовательностных машин и их отображений
3.1. Основные понятия и определения
3.2. Место классов линейных последовательностных машин в иерархии классов конечных детерминированных автоматов
3.2.1. Перечисление конечных детерминированных автоматов

3.2.2. Перечисление линейных последовательностных
машин
3.3. Место классов билинейных систем в иерархии классов конечных детерминированных автоматов
3.4. Непредставимые отдельными классами ЛПМ отображения
Литература
Приложение 1
Приложение 2
Приложение 3

ВВЕДЕНИЕ
Конечные детерминированные автоматы являются дискретными структурами, имеющими приложение на практике и в теории алгоритмов. В прикладных областях автоматы определяют фундаментальный класс преобразователей информации произвольной природы: в технике, биологии, экономике и т.д.
Если разделять определение автомата и способы задания автоматов, то конечные детерминированные автоматы соответствуют словарным функциям и задаются с помощью распространенных дискретных конструкций: матриц, таблиц, графов, канонических уравнений, формул языка регулярных выражений и т.д.
В классических способах задания автоматов дискретная словарная функция представлена некоторым, порождающим функцию базисом, состоящим из конечного набора побуквенных преобразований, с последовательным применением функций базиса к слову-аргументу функции. В связи с этим анализ поведения автоматов, то есть фрагментов словарных функций, затруднен, так как в сжатом базисе, как правило, трудно предвидеть свойства, проявляющиеся в развернутом виде (при последующем вычислении функции).
Традиционно исследование поведения автоматов было явно или не явно ориентировано на выяснение возможностей конечных детерминированных автоматов, при этом, то, что не могут делать автоматы иллюстрировалось примерами, показывающими место класса конечных детерминированных автоматов в иерархии математических автоматов.
В диссертации исследуются свойства и отношения, которыми не обладают или класс конечных детерминированных автоматов в целом, или его подклассы.
Цель работы состоит в нахождении зависимости свойств непредставимых автоматами преобразований от объема памяти автомата и от свойств структур, определяющих автоматы специальных классов (линейных и билинейных последовательностных машин).
Для достижения указанной цели были поставлены задачи
- аналитического описания недопускаемых рассматриваемыми ав-

2. СВОЙСТВА ГЕОМЕТРИЧЕСКИХ ОБРАЗОВ АВТОМАТОВ И КЛАССОВ АВТОМАТОВ
2.1. Словарная геометрия и построение геометрических образов автоматов
Теория экспериментов с автоматами широко используется в технической диагностике, в связи с этим возникла необходимость в теории построения тестов.
До тех пор, пока диагностируемые системы были просты и могли быть представлены автоматами с небольшим числом состояний, были эффективны переборные методы и основанные на них алгоритмы построения тестов и диагностирования.
Первоначальная интуитивная обозримость задач и простота методов построения тестов для КД-автоматов с небольшим числом состояний позволили теории ’’обходиться без мощных математических идеализаций числовой непрерывности, бесконечно малого, предельных переходов, актуальной бесконечности и т.п. В методах технического диагностирования в основном использовались идеи сведения переборов по бесконечным множествам к переборам по конечным множествам, интуиция и явное построение таблиц, матриц графов и т.п.” [30]
При переходе к диагностированию автоматов с большим числом состояний таких средств оказалось недостаточно. В связи с этим предлагается геометрический подход к диагностированию поведения математических автоматов, который позволяет применить дискретные аналоги методов непрерывной математики для построения геометрических образов поведения автоматов, постановок задач и поиска решений задач.
Этот подход был впервые предложен В.А.Твердохлебовым, и рассматривался им в статьях и монографиях [30],[33].
Принципиально важными этапами предложенного В.А. Твердох-лебовым геометрического подхода к диагностированию являются:
- построение дискретной словарной геометрии Г о, в которой геометрическим образом автомата является реализуемое им автоматное отображение (для инициальных автоматов) или объединение автоматных отображений по всем возможным начальным состояниям,