Аннотация. Предложен алгоритм определения эквивалентности многоленточных автоматов, представленных в виде графов, основанный на доказанной автором теореме о достаточных условиях эквивалентности. Алгоритм состоит в построении специальной (замкнутой) диаграммы с помощью элементарных операций, предложенных M. Бердом. Сформулированы правила применения этих операций, которые позволяют сделать алгоритм конечным.
Ключевые слова: многоленточный автомат, детерминированный автомат, эквивалентность.
Борисенко Виктор Иванович,
кандидат физ.-мат. наук, Киев,
e-mail: borisen@ukr.net.