Part 3. Mathematical models

Applying negation to strongly connected automata

D. O. Maslenikov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

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