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

Muravev Nikita Valerievich

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

Muravev N. V.

Muravev Nikita Valerievich

graduate student, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Received: 25 Mar 2026

Published: 2025, vol. 29, issue 3, pp. 180–189

Download full text (In Russian)

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

BibTeX

@article{IS-Muravev2025,
  author  = {Muravev, Nikita Valerievich},
  title   = {{The order problem for automata which transition and output functions lie in closed Post classes}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2025},
  volume  = {29},
  number  = {3},
  pages   = {180--189},
}

AMSBIB

\Bibitem{IS-Muravev2025}
\by N.\,V.~Muravev
\paper The order problem for automata which transition and output functions lie in closed Post classes
\jour Intelligent Systems. Theory and Applications
\yr 2025
\vol 29
\issue 3
\pages 180--189
\lang In Russian

Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue