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