ИСТИНА

Конечные автоматы-преобразователи (трансдьюсеры) отличаются от обычных автоматов Мили тем, что в ответ на входной сигнал (букву) они вырабатывают в качестве отклика целое слово. Это отличие позволяет использовать трансдьюсеры в более разнообразных приложениях (для моделирования реагирующих программ, роботов, коммутационных устройств), но существенно осложняет задачу анализа их поведения. Так, например, известно, что проблема проверки свойства тотальности (способности порождать любое слово) для недетерминированных трансдьюсеров алгоритмически неразрешима. Поэтому заслуживает внимания задача выделения классов трансдьюсеров, для которых эта и подобные ей проблемы проверки функциональных свойств имеют эффективное решение. Мы выделили новый класс недетерминированных трансдьюсеров, для которых задачи проверки эквивалентности и минимизации могут быть решены за полиномиальное время.