Исследование живых и безопасных решений параллельных уравнений и неравенств на множестве полуавтоматов и автоматов

• Автор: Буфалов, Сергей Анатольевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Томск
• Количество страниц: 144 с. : ил

ОГЛАВЛЕНИЕ
Введение

1 Основные понятия. Обзор литературы

1.1 Формальные языки

1.1.1 Определения

1.1.2 Параллельная композиция языков

1.1.3 Регулярные и конечно-автоматные языки

1.2 Конечные полуавтоматы

1.2.1 Определения

1.2.2 Отношения на множестве полуавтоматов

1.2.3 Операции на множестве полуавтоматов
1.2.4 Параллельная композиция полуавтоматов
1.2.5 Уравнения и неравенства на множестве
полуавтоматов
1.2.5.1 Живое решение
1.2.5.2 Безопасное решение
1.2.6 Обзор существующих подходов, к решению
уравнений и неравенств на множестве полуавтоматов
1.3 Конечные автоматы
1.3.1 Определения
1.3.2 Взаимосвязь между полуавтоматами и автоматами
1.3.3 Параллельная композиция автоматов
1.3.4 Уравнения и неравенства на множестве автоматов
1.3.5 Обзор существующих подходов к решению
уравнений и неравенств на множестве автоматов
1.4 Обзор задач, сводящихся к решению уравнений и
неравенств
1.4.1 Логический синтез
1.4.2 Диагностика компоненты автоматной сети
1.4.3 Оптимизация компоненты автоматной сети
1.5 Выводы по главе
2 ПОЛУАВТОМАТНЫЕ УРАВНЕНИЯ И НЕРАВЕНСТВА
2.1 Решение неравенства А0ех1Х< С
2.1.1 Множество решений неравенства

2.1.2 Живые решения
2.1.2.1 Живые решения, реализующие конечный язык
2.1.2.2 Совершенный полуавтомат
2.1.2.3 Отношение Re-моделирования
2.1.2.4 Характеризация редукций живого решения, являющихся живыми решениями
2.1.2.5 Наибольшая редукция решения,
являющаяся живым решением
2.1.3 Безопасные решения
2.1.4 Живые безопасные решения
2.2 Результаты компьютерных экспериментов
2.2.1 Теоретические оценки сложности наибольшего и наибольшего живого решений
2.2.2 Зависимость числа состояний решений от числа состояний в контексте и спецификации
2.2.3 Зависимость числа состояний решений от
мощности алфавитов
2.3 Выводы по главе
3 АВТОМАТНЫЕ УРАВНЕНИЯ И НЕРАВЕНСТВА
3.1 Решение автоматного неравенства А 0Х< С
3.1.1 Множество решений неравенства
3.1.2 Живые решения
3.1.3 Безопасные решения
3.1.4 Живые безопасные решения
3.2 Решение неравенства А 0Х< С для
полностью определённых автоматов
3.2.1 Множество решений неравенства
3.2.2 Живые решения
3.2.3 Безопасные решения
3.2.4 Живые безопасные решения
3.3 Решение уравнения АФХ= С
3.4 Решение неравенства А0Х>С
3.5 Выводы по главе
Заключение
Литература

ВВЕДЕНИЕ
Общая характеристика работы
Актуальность проблемы. Сложные системы логического управления обычно реализуются сетью из взаимодействующих компонент [1 - 4]. Благодаря этому в теории дискретных систем решение ряда задач логического синтеза [3, 5 - 21], управления [4, 22 - 32] и оптимизации [10, 33] может быть сведено к решению уравнения А°Х&С. Здесь А и X описывают поведение, соответственно, известной и неизвестной компонент синтезируемой системы, - оператор композиции и “и” - отношение (конформности), в котором должны находиться поведение синтезируемой системы и {эталонное) поведение реализуемой системы С (спецификации).
Подобным образом, например, формализуются задачи синтеза цифровых контроллеров [23] и покомпонентной оптимизации дискретных систем [34]. В первом случае А описывает поведение множества компонент, которыми контроллер должен управлять так, чтобы реализовать нужное поведение С. Поведение же самого контроллера описывается одним из решений уравнения А°А»С. Если уравнение обладает хотя бы одним решением, то имеет смысл говорить о нахождении оптимального (например, в смысле числа состояний) решения, т.к. наибольший интерес представляют именно оптимальные реализации контроллера. Во втором случае предполагается, что все компоненты, кроме одной, реализованы оптимально, и А описывает их совместное поведение, а свободная переменная X соответствует компоненте, подлежащей оптимизации. Среди решений уравнения находится оптимальное (которое и подставляется вместо оптимизируемой компоненты), и процесс продолжается до тех пор, пока все компоненты не будут оптимизированы.
Следует заметить, что не всякое решение уравнения А°Х&С пригодно с точки зрения практики. Особый интерес представляют те решения, которые позволяют оптимизировать компоненту (синтезируемую посредством решения логического уравнения А0Х<*С) в смысле её внутреннего взаимодействия с другими компонентами сети. К классу таких решений относятся рассматриваемые в работе живые и безопасные решения.
Тот факт, что решение является живым, гарантирует отсутствие в

держит тройку (W,v,W), где W,W'qS, если W'={s'3seW ((s, v, s’) е <$>)}. Полностью определённую форму построенного полуавтомата обозначим через Dfa(E) и назовём детерминированной формой полуавтомата Р, а операцию её построения - детерминизацией полуавтомата Р. По определению, число состояний детерминированной формы экспоненциально зависит от числа детерминизируемого полуавтомата. Алгоритмические реализации процедуры детерминизации можно найти в работах [41, 70, 71].
На рисунке 1.2.5.3 приведён пример построения детерминированной формы полуавтомата Р, изображённого на рисунке 1.2.5.1.
Ниже вводятся операции, соответствующие теоретико-языковым операциям. Каждая из них иллюстрируются на примере полуавтоматов, изображённых на рисунках 1.2.6.1 и 1.2.6.2.
Если V,S,to,F) - детерминированная форма полуавтомата Р, то дополнением полуавтомата Р назовём полуавтомат P={T,V,S,to,TF), полученный из детерминированной формы полуавтомата Р путём объявления её финальных состояний нефинальными и наоборот. Дополнение полуавтомата Р реализует дополнение языка ЦР). Согласно определению, дополнение является детерминированным полуавтоматом. Пример построения дополнения полуавтомата, изображённого на рисунке 1.2.6.2, приведён на рисунке 1.2.6.3.
Если пересечение Vn W не пусто, то пересечением полуавтоматов Р и R назовём полуавтомат PnR={SxQ,VnJV,S,(so,qo),PpxPit), отношение переходов которого содержит тройку ((s,q),a,(s',q')), если и только если (s,a,s')eSp и (q,a,q')eSR. Пересечение полуавтоматов Р и R реализует пересечение языков ЦР) и ЦР). По определению, если полуавтоматы Р и R недетерминированные, то результатом операции может быть недетерминированный полуавтомат. Пример построения пересечения полуавтоматов, изображённых на рисунках 1.2.6.1 и 1.2.6.2, приведён на рисунке 1.2.6.4.
Если алфавиты V и W не пересекаются, то пересечение полуавтоматов Р и R не определено. Имеет место следующее утверждение.
Утверждение 1.2.2. Пусть Р - детерминированный полуавтомат, R - его редукция и