|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Полиномиальный алгоритм проверки эквивалентности слабо недетерминированных конечных автоматов-преобразователейстатья
- Авторы: Захаров В.А., Джусупекова З.А.
- Сборник: Дискретные модели в теории управляющих систем: Х Международная конференция, Москва и Подмосковье, 23-25 мая 2018 г. : Труды
- Редакторы: Алексеев Валерий Борисович, Данилов Борис Радиславович, Романов Дмитрий Сергеевич
- Серия: 978-5-317-05834-0
- Том: 1
- Год издания: 2018
- Издательство: ООО "МАКС Пресс"
- Местоположение издательства: Москва
- Первая страница: 134
- Последняя страница: 136
- Аннотация: Конечные автоматы-преобразователи (трансдьюсеры) отличаются от обычных автоматов Мили тем, что в ответ на входной сигнал (букву) они вырабатывают в качестве отклика целое слово. Это отличие позволяет использовать трансдьюсеры в более разнообразных приложениях (для моделирования реагирующих программ, роботов, коммутационных устройств), но существенно осложняет задачу анализа их поведения. Так, например, известно, что проблема проверки свойства тотальности (способности порождать любое слово) для недетерминированных трансдьюсеров алгоритмически неразрешима. Поэтому заслуживает внимания задача выделения классов трансдьюсеров, для которых эта и подобные ей проблемы проверки функциональных свойств имеют эффективное решение. Мы выделили новый класс недетерминированных трансдьюсеров, для которых задачи проверки эквивалентности и минимизации могут быть решены за полиномиальное время.
- Добавил в систему: Захаров Владимир Анатольевич