Алгоритм, устанавливающий эквивалентность детерминированных многоленточных автоматов

• Опубліковано в: : Кибернетика и системный анализ
• Дата: 2015
• Автор: Борисенко, В.И.
• Формат: Стаття
• Мова: Російська
• Опубліковано: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
• Теми: Кибернетика
• Онлайн доступ: https://nasplib.isofts.kiev.ua/handle/123456789/124907
• Назва журналу: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Цитувати: Алгоритм, устанавливающий эквивалентность детерминированных многоленточных автоматов / В.И. Борисенко // Кибернетика и системный анализ. — 2015. — Т. 51, № 5. — С. 63-72. — Бібліогр.: 9 назв. — рос.

Предложен алгоритм определения эквивалентности многоленточных автоматов, представленных в виде графов, основанный на доказанной автором теореме о достаточных условиях эквивалентности. Алгоритм состоит в построении специальной (замкнутой) диаграммы с помощью элементарных операций, предложенных M. Бердом. Сформулированы правила применения этих операций, которые позволяют сделать алгоритм конечным. Запропоновано алгоритм, який визначає еквівалентність багатострічкових автоматів, зображених у вигляді графів, та базується на доведеній автором теоремі про достатні умови еквівалентності. Алгоритм полягає в побудові спеціальної (замкненої) діаграми за допомогою елементарних операцій, запропонованих M. Бердом. Сформульовано правила застосування цих операцій, які дозволяють зробити алгоритм скінченним. This paper proposes an algorithm to determine the equivalence of multitape automata presented in the form of graphs. The algorithm is based on the theorem (proved by the author) on the sufficient conditions of equivalence and consists in the construction of special (closed) diagrams with the help of elementary operations proposed by M. Bird. The rules for the application of these operations, which make the algorithm finite, are formulated.