|
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.
Citation:
M. V. Karandashov, “About transitive property of mappings associated with a finite state machines from the groups $AS_p$”, Prikl. Diskr. Mat. Suppl., 2016, no. 9, 115–118
Linking options:
https://www.mathnet.ru/eng/pdma273 https://www.mathnet.ru/eng/pdma/y2016/i9/p115
|
Statistics & downloads: |
Abstract page: | 127 | Full-text PDF : | 34 | References: | 25 |
|