Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

On the order of some automata with the superposition operation..

Abstract

If the input and output alphabets of an initial automaton coincide, then the number of distinct automata obtained by superposing the original automaton with itself can be either finite or infinite. The problem of determining the order of a finite initial automaton with respect to superposition is algorithmically undecidable in the general case. However, for some classes of automata, algorithms for determining the order can be found.

Keywords: Mealy automata, Post classes, algorithmic decidability.

BibTeX
@article{IS-Babin-Muravev2026,
  author  = {Babin, Dmitry Nikolaevich and Muravev, Nikita Valerievich},
  title   = {{On the order of some automata with the superposition operation..}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {62--65},
}
AMSBIB
\Bibitem{IS-Babin-Muravev2026}
\by D.\,N.~Babin, N.\,V.~Muravev
\paper On the order of some automata with the superposition operation..
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 62--65
\lang In Russian
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover