On the additive shift property for the linear realizability of
automata

Rodin Sergei Borisovich

On the additive shift property for the linear realizability of automata

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 2, pp. 52–66

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 additive shift property for the linear realizability of automata}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2024},
  volume  = {28},
  number  = {2},
  pages   = {52--66},
}

AMSBIB

\Bibitem{IS-Rodin2024}
\by S.\,B.~Rodin
\paper On the additive shift property for the linear realizability of automata
\jour Intelligent Systems. Theory and Applications
\yr 2024
\vol 28
\issue 2
\pages 52--66
\lang In Russian

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

← Back to issue