Applying negation to strongly connected automata

Maslenikov Denis Olegovich

Applying negation to strongly connected automata

Maslenikov D. O.

Maslenikov Denis Olegovich

student, Lomonosov Moscow State University, Faculty of Mechanics and Mathematics, Chair of Mathematical Theory of Intellectual Systems

Received: 25 Mar 2026

Published: 2025, vol. 29, issue 3, pp. 164–179

Download full text (In Russian)

Abstract

The concept of the result of applying a function f, defined on its output alphabet, to an initial automaton is introduced as a minimized initial automaton implementing a certain boundedly deterministic function. A suficient condition for its strong connectivity is found. The concepts of a skeleton - a noninitial automaton without an output function - and the result of applying a function to it, as a noninitial analog of the previous definition, are also introduced. The results of applying negation to skeletons of a certain type are considered. For the result of applying negation to a strongly connected automaton with input and output alphabets {0,1}, upper and lower bounds for the number of states are obtained, for which a generalization of the concept of a cycle space to oriented graphs was considered.

Keywords: finite automaton, self-modifying finite state machine, Moore diagram, graph, cycle space.

BibTeX

@article{IS-Maslenikov2025,
  author  = {Maslenikov, Denis Olegovich},
  title   = {{Applying negation to strongly connected automata}},
  journal = {Intelligent Systems. Theory and Applications},
  year    = {2025},
  volume  = {29},
  number  = {3},
  pages   = {164--179},
}

AMSBIB

\Bibitem{IS-Maslenikov2025}
\by D.\,O.~Maslenikov
\paper Applying negation to strongly connected automata
\jour Intelligent Systems. Theory and Applications
\yr 2025
\vol 29
\issue 3
\pages 164--179
\lang In Russian

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

← Back to issue