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/

[1] Benois M., “Parties rationnelles du groupe libre”, C. R. Acad. Sci. Paris, Sér. A, 269 (1969), 1188–1190 | MR | Zbl

[2] Davey B. A, Priestley H. A., Introduction to Lattices and Order, Cambridge Univ. Press, 2002 | DOI | MR | Zbl

[3] Eder E., “Properties of substitutions and unifications”, J. Symb. Comput., 1:1 (1985), 31–46 | DOI | MR | Zbl

[4] Eilenberg S., Automata, Languages, and Machines, v. A, Acad. Press, 1974, 451 pp. | MR | Zbl

[5] Furst M., Hopcroft J., Luks E., “Polynomial-time algorithms for permutation groups”, 21st Annu. Symp. Found. Comput. Sci., IEEE Computer Soc., 1980, 36–41 | DOI | MR

[6] Grunschlag Z., Algorithms in Geometric Group Theory, PhD thesis, Univ. California, Berkeley, 1999 | MR

[7] Jerrum M., “A compact representation for permutation groups”, J. Algorithms, 7:1 (1986), 60–78 | DOI | MR | Zbl

[8] Kambites M., Silva P. V., Steinberg B., “On the rational subset problem for groups”, J. Algebra, 309:2 (2007), 622–639 | DOI | MR | Zbl

[9] Lohrey M., “The rational subset membership problem for groups: a survey”, Groups St Andrews 2013, London Math. Soc. Lect. Note Ser., Cambridge Univ. Press, 2015, 368–389 | DOI | MR | Zbl

[10] Sakarovitch J., Elements of Automata Theory, Cambridge Univ. Press, 2009 | DOI | MR | Zbl