Almost unary bases of automata under superposition.

Babin Dmitry Nikolaevich

Almost unary bases of automata under superposition.

Babin D. N.

Babin Dmitry Nikolaevich

Doctor of Physical and Mathematical Sciences, Prof., Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Received: 30 Mar 2026 Revised: 18 May 2026 Accepted: 19 May 2026

Published: 2026, vol. 30, issue 3, pp. 142–150

Download full text (In Russian)

Abstract

For systems of automaton functions that form a closed class, it is important to determine the basis from the minimal number of variables from which they can be obtained by superposition operations. Of particular interest are classes in which the ’proper’ automata from the basis have a single input variable; this restriction does not apply to Boolean functions from the basis, which are automata with a single state. An example of such a class is the class of all automata. The author studies subclasses of automata whose transition and output functions belong to a certain Post class.

Keywords: arity, automaton, Boolean function, superposition, closed class.

BibTeX

@article{IS-Babin2026,
  author  = {Babin, Dmitry Nikolaevich},
  title   = {{Almost unary bases of automata under superposition.}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {3},
  pages   = {142--150},
}

AMSBIB

\Bibitem{IS-Babin2026}
\by D.\,N.~Babin
\paper Almost unary bases of automata under superposition.
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 3
\pages 142--150
\lang In Russian

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

← Back to issue