RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2021 Volume 33, Issue 1, Pages 82–90 (Mi dm1633)

This article is cited in 2 papers

On the membership problem for finite automata over symmetric groups

A. A. Khashaev

Lomonosov Moscow State University

Abstract: 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.

UDC: 519.713

Received: 19.01.2021

DOI: 10.4213/dm1633


 English version:
Discrete Mathematics and Applications, 2022, 32:6, 383–389


© Steklov Math. Inst. of RAS, 2025