On the linear realizability property of the mappings

Rodin Sergei Borisovich

On the linear realizability property of the mappings

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 Intellectual Systems

Published: 2024, vol. 28, issue 1, pp. 98–110

Download full text (In Russian)

Abstract

This paper studies the property of linear realizability of mapping of the finite set into itself. This property is important from linear realizability of automata, namely linear realizability of the elements of the generating set of the automaton inner semigroup is the one of the necessary conditions for linear realizability of the automaton. Previously it was shown that every mapping of the finite set into itself is linear realizable via an encoding which code length is equal the finite set cardinality. In this paper this result will be improved and it will be shown that every mapping of the finite set into itself is linear realizable via an encoding which code length is equal the finite set cardinality minus one.

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

BibTeX

@article{IS-Rodin2024,
  author  = {Rodin, Sergei Borisovich},
  title   = {{On the linear realizability property of the mappings}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2024},
  volume  = {28},
  number  = {1},
  pages   = {98--110},
}

AMSBIB

\Bibitem{IS-Rodin2024}
\by S.\,B.~Rodin
\paper On the linear realizability property of the mappings
\jour Intelligent Systems. Theory and Applications
\yr 2024
\vol 28
\issue 1
\pages 98--110
\lang In Russian

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

← Back to issue