Mappings with maximum implementation complexity

Rodin Sergei Borisovich

Mappings with maximum implementation complexity

Rodin S. B.

Rodin Sergei Borisovich

Candidate of Physical and Mathematical Sciences, Senior research scientist, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intelligent Systems

Received: 28 Apr 2026 Revised: 26 Jun 2026 Accepted: 13 Jul 2026

Published: 2026, vol. 30, issue 3, pp. 126–140

Download full text (In Russian)

Abstract

The paper continues the investigation into the complexity of automata implementation via state encoding. Previous research was focused on the identification of “simple implementations” of automata and mappings on a finite set. This paper is devoted to mappings with “complex implementations”, i.e., mappings for which any irredundant encoding yields a Boolean operator of maximum complexity in terms of the Zhegalkin polynomial degree. It is proved that for any set cardinality \(n=2^k\) such mappings exist. These mappings can be used in future research to prove that automata admitting only “complex implementations” also exist.

Keywords: Automata theory, semiautomata, transition systems, assignment, state encoding, complexity, boolean operator.

BibTeX

@article{IS-Rodin2026,
  author  = {Rodin, Sergei Borisovich},
  title   = {{Mappings with maximum implementation complexity}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2026},
  volume  = {30},
  number  = {3},
  pages   = {126--140},
}

AMSBIB

\Bibitem{IS-Rodin2026}
\by S.\,B.~Rodin
\paper Mappings with maximum implementation complexity
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 3
\pages 126--140
\lang In Russian

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

← Back to issue