Оптимизация многокомпонентных дискретных систем на основе решения автоматных уравнений

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

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

1. Основные определения. Постановка задачи оптимизации на основе автоматной модели

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

1.1.1 Конечные автоматы.

1.1.2 Операции над автоматами и полуавтоматами

1.1.3 Синхронная композиция двух автоматов

1.1.4 Многокомпонентная синхронная композиция.

1.2 Постановка задачи оптимизации на основе решения автоматных уравнений

1.2.1 Задача оптимизации.

1.2.2 Определение автоматного уравнения для двухкомпонентной сети

1.3 Методы решения бинарных автоматных уравнений.
1.3.1 Решение уравнения на основе безразличных последовательностей.
1.3.2 Решение уравнения на основе автомата
1.3.3 Языковый подход к решению автоматных уравнений.
1.4 Критерии оптимизации.
1.5 Выводы по главе
2. Использование автоматных уравнений для оптимизации многокомпонентной композиции.
2.1 Многокомпонентная синхронная композиция
2.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.4 Основные результаты главы
3. Покомпонентная оптимизация дискретных систем относительно различных критериев
3.1 Глобальная оптимизация.
3.2 Локальная оптимизация
3.2.1 Локальная оптимизация посредством решения множества автоматных уравнений.
3.2.2 Локальная оптимизация посредством решения системы уравнений
3.3 Критерии оптимизации
3.3.1 Число связей в автоматной сети
3.3.1.1 О минимизации числа связей на основе решения автоматного уравнения.
3.3.1.2 Нахождение наибольшего решения автоматного уравнения с заданным множеством входных алфавитов.
3.3.1.3 Минимизация числа входных переменных компоненты
3.3.2 Отказоустойчивость компоненты
3.3.3 Число вентилей в логической реализации компоненты
3.4 Основные результаты главы.
4. Прогрессивные решения автоматных уравнений и систем автоматных уравнений.
4.1 Наибольшее прогрессивное решение автоматного уравнения
4.2 Характеризация прогрессивных решений
4.3 Прогрессивные решения системы уравнений.
4.4 Экспериментальные результаты по существованию прогрессивных решений.
4.5 Основные результаты главы.
Заключение.
Литература


Показано, что в этом случае общим решением автоматного уравнения является частичный детерминированный автомат Largest; то есть в качестве хвостовой компоненты можно использовать любой автомат, квазиэквивалентный автомату Largest. Методы решения автоматного уравнения для головной компоненты последовательной сети [, ] появились значительно позже и основывались на использовании вхо до-выходных последовательностей компоненты, которые являются эквивалентными с точки зрения внешнего поведения. Методы решения уравнения, соответствующего двухкомпонентной сети с обратными связями, предложены в работах [, , ]. В работе [] для решения автоматного уравнения используется специальный недетерминированный 5-автомат, который эквивалентен наибольшему решению уравнения. Для построения 5-автомата используется вычисление с неподвижной точкой. В работе [] предложен метод нахождения наибольшего решения автоматного уравнения на основе решения уравнения в алгебре регулярных языков. Наибольшее решение Largest уравнения можно рассматривать как резервуар, из которого выбирается оптимальное решение согласно некоторому критерию. Однако не каждое решение уравнения интересно с практической или теоретической точки зрения. Если поведение компоненты должно быть определено для любой входной последовательности, то в качестве решений могут быть выбраны только полностью определенные решения. При логическом синтезе систем с обратными связями необходимо гарантировать отсутствие тупиков в рассматриваемой системе, то есть потребовать, чтобы на любую внешнюю входную последовательность. Решение автоматного-уравнения с таким свойством называется прогрессивным. Достаточные условия синтеза двухкомпонентной автоматной сети без тупиков хорошо1 известны [, ]. В частности, таким условием является использование-автоматов Мура или, по крайней мере, наличие автомата Мура в каждой цепи* обратной связи. Прогрессивные решения автоматного уравнения не. Мура, однако полное описание всех пршрессивных решений остается не известным. Известно только [], что если прогрессивное решение существует, то существует и наибольшее прогрессивное решение. Любое решение автоматного уравнения является редукцией наибольшего решения уравнения. Обратное не всегда верно, то есть [] не всякая полностью определенная редукция такого решения также является решением уравнения. Кроме того, не каждое решение автоматного уравнения подходит для практической реализации. Таким образом, с теоретической точки зрения остается открытым вопрос о полном описании решений автоматного уравнения, а именно, какие из редукций наибольшего решения можно использовать при оптимизации соответствующей компоненты. С практической точки зрения, существующие методы нахождения наибольшего решения автоматного уравнения имеют экспоненциальную сложность, что затрудняет их применение для систем большой размерности. Поэтому, с одной стороны, необходимо уменьшить размерность автоматов-коэффициентов уравнения, а, с другой стороны, находить, возможно, часть наибольшего решения, которая является достаточно представительной и может быть найдена за достаточно короткое время. Необходимо также отметить, что до сих пор в качестве единственного критерия при использовании автоматных уравнений с целью оптимизации компоненты автоматной сети рассматривается число состояний компоненты [-, , ]. Данный критерий представляет скорее теоретический интерес, так как уменьшение числа состояний не всегда приводит к упрощению логической реализации. Необходимо исследовать другие критерии оптимизации, такие как число связей в автоматной сети, отказоустойчивость компоненты и т. Вторая глава диссертации посвящена решению автоматных уравнений. Напомним, что практически все методы решения автоматных уравнений разработаны для двухкомпонентной композиции автоматов. Обычно [, , ] понятие автоматного уравнения вводится для бинарной автоматной сети конкретной заданной структуры; тогда как в общем случае дискретная система может быть представлена композицией более чем двух компонент. Поэтому в данной работе мы вводим понятие автоматного уравнения для автоматной сети с произвольной структурой и произвольным числом компонент. Для этого в параграфе 2.