ИСТИНА

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