Applied Theory of Automata and Graphs

About transitive property of mappings associated with a finite state machines from the groups $AS_p$

M. V. Karandashov

Saratov State University, Saratov

Abstract: Checking the transitive property of the automaton mappings is discussed. A general criterion for transitivity of automaton mappings on words of length $k\in\mathbb N$ is presented. For automata from groups $AS_p$, an algorithm for checking transitive property is proposed. The complexity of the algorithm depends on the number of automaton states and does not depend on the input word length. The upper bound of the algorithm complexity is specified.

Keywords: finite state machines, automata mappings, $AS_p$ groups, transitivity.

UDC: 519.7

DOI: 10.17223/2226308X/9/46