On the membership problem for finite automata over symmetric groups

被引：0

作者：

Khashaev A.A. ^{[1
]}

机构：

[1] Lomonosov Moscow State University, Moscow

来源：

Discrete Mathematics and Applications | 2022年 / 32卷 / 06期

关键词：

computational complexity; finite automata; groups; permutations;

D O I：

10.1515/dma-2022-0033

中图分类号：

学科分类号：

摘要：

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. © 2022 Walter de Gruyter GmbH, Berlin/Boston.

引用

页码：389 / 395

页数：6

共 10 条

[1] Benois M., parties rationnelles du groupe libre, C. R. Acad. Sci. Paris, Ser. A, 269, pp. 1188-1190, (1969)
[2] Davey B.A., Priestley H.A., Introduction to Lattices and Order, (2002)
[3] Eder E., properties of substitutions and unifications, J. Symb. Comput., 1, 1, pp. 31-46, (1985)
[4] Eilenberg S., Automata, Languages, and Machines. Volume A, (1974)
[5] Furst M., Hopcroft J., Luks E., polynomial-time algorithms for permutation groups, 21st Annu. Symp. Found. Comput. Sci., IEEE Computer Soc., pp. 36-41, (1980)
[6] Grunschlag Z., Algorithms in Geometric Group Theory, (1999)
[7] Jerrum M., a compact representation for permutation groups, J. Algorithms, 7, 1, pp. 60-78, (1986)
[8] Kambites M., Silva P.V., Steinberg B., on the rational subset problem for groups, J. Algebra, 309, 2, pp. 622-639, (2007)
[9] Lohrey M., Groups St Andrews 2013, London Math. Soc. Lect. Note Ser., pp. 368-389, (2015)
[10] Sakarovitch J., Elements of Automata Theory, (2009)

← 1 →