![]() |
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Показано, как свести задачу проверки эквивалентности детерминированных 2-ленточных конечных автоматов к задаче проверки эквивалентности слабо недетерминированных трансдьюсеров, которая разрешима за полиномиальное время. Это новый метод проверки эквивалентности 2-ленточных автоматов, и он применим для проверки некоторых видов детерминированных автоматов с произвольным числом лент.