Part 3. Mathematical models

The order problem for automata which transition and output functions lie in closed Post classes

N. V. Muravev

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: We consider the order problem for Mealy automata with respect to the superposition operation. The splitting of the Post’s lattice of closed classes is proved based on decidability of the order problem for respective $R$-automata.

Keywords: Mealy automata, Post classes, algorithmic decidability