Geodesic
On the membership problem for~finite automata over~symmetric groups
Diskretnaya Matematika, Tome 33 (2021) no. 1, pp. 82-90

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider automata in which transitions are labelled with arbitrary permutations. The language of such an automaton consists of compositions of permutations for all possible admissible computation paths. The membership problem for finite automata over symmetric groups is the following decision problem: does a given permutation belong to the language of a given automaton? We show that this problem is NP-complete. We also propose an efficient algorithm for the case of strongly connected automata.
Keywords: finite automata, groups, permutations, computational complexity. 
@article{DM_2021_33_1_a6,
     author = {A. A. Khashaev},
     title = {On the membership problem for~finite automata over~symmetric groups},
     journal = {Diskretnaya Matematika},
     pages = {82--90},
     publisher = {mathdoc},
     volume = {33},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2021_33_1_a6/}
}
TY  - JOUR
AU  - A. A. Khashaev
TI  - On the membership problem for~finite automata over~symmetric groups
JO  - Diskretnaya Matematika
PY  - 2021
SP  - 82
EP  - 90
VL  - 33
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2021_33_1_a6/
LA  - ru
ID  - DM_2021_33_1_a6
ER  - 
%0 Journal Article
%A A. A. Khashaev
%T On the membership problem for~finite automata over~symmetric groups
%J Diskretnaya Matematika
%D 2021
%P 82-90
%V 33
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2021_33_1_a6/
%G ru
%F DM_2021_33_1_a6
A. A. Khashaev. On the membership problem for~finite automata over~symmetric groups. Diskretnaya Matematika, Tome 33 (2021) no. 1, pp. 82-90. http://geodesic.mathdoc.fr/item/DM_2021_33_1_a6/