Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Contents
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 512.9
Borisenko V.I.

THE ALGORITHM FOR ESTABLISHING THE EQUIVALENCE OF DETERMINED MULTITAPE AUTOMATA

Abstract. 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.

Keywords: automaton, multitape, deterministic, equivalence.



FULL TEXT

Борисенко Виктор Иванович,
кандидат физ.-мат. наук, Киев,
e-mail: borisen@ukr.net.

© 2016 Kibernetika.org. All rights reserved.