On the order of some automata with the superposition operation..
Received: 01 Oct 2026 Revised: 19 Oct 2026 Accepted: 22 Oct 2026
Published: 2026, vol. 30, issue 4, pp. 62–65
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
RU