|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
О минимизации конечных автоматов-преобразователей над полугруппамистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Авторы: Захаров В.А., Темербекова Г.Г.
- Журнал: Моделирование и анализ информационных систем
- Том: 23
- Номер: 6
- Год издания: 2016
- Издательство: Яросл. гос. ун-т
- Местоположение издательства: Ярославль
- Первая страница: 741
- Последняя страница: 753
- Аннотация: Автоматы-преобразователи над полугруппами можно использовать в качестве модели последовательных реагирующих программ, работающих в постоянном взаимодействии со своим окружением. Получив очередную порцию данных, реагирующая программа выполняет некоторую последовательность действий и предъявляет результат. Такие программы возникают при проектировании компьютерных драйверов, алгоритмов, работающих в оперативном режиме, сетевых коммутаторов. Во многих случаях проблема верификации программ такого рода может быть сведена к задачам минимизации и проверки эквивалентности конечных автоматов-преобразователей. Минимизация преобразователей над полугруппами проводится в три этапа. Вначале для всех состояний преобразователя вычисляются наибольшие общий левые делители. Затем все вычисленные делители ''поднимаются вверх'' по переходам преобразователя, и в результате образуется приведенный преобразователь. Наконец, для минимизации приведенных преобразователей применяются методы минимизации классических конечных автоматов-распознавателей.
- Добавил в систему: Захаров Владимир Анатольевич