Минимальность и тупиковость многоленточных автоматов

Рассматривается класс $M$ детерминированных бинарных двухленточных автоматов, для которых состояния автомата, в которых происходит считывание с добавочной второй ленты, позволяют продолжить вычисления только в том случае, когда считываемый символ является фиксированным для всех автоматов. Для автоматов из класса $M$ решается так называемая обобщенная проблема минимизации. Эта проблема состоит в том, чтобы для всякого класса эквивалентных автоматов из $M$ найти в этом классе все минимальные по числу состояний автоматы. В статье доказана разрешимость обобщенной проблемы минимизации в $M$, описана и проанализирована процедура ее решения.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 06–01–00106.