On the cardinality computation problem for regular language over symmetric groups

Recieved: 08/26/2023

Accepted: 01/14/2024

Published: 04/02/2024

Keywords: regular languages, finite automata, groups, permutations, computational complexity

To cite this article

Khashaev A. A. On the cardinality computation problem for regular language over symmetric groups. // Moscow University Journal. Series 15. Computational Mathematics and Cybernetics. 2024. N 2, p.58-64 https://doi.org/10.55959/MSU/0137-0782-15-2024-47-2-58-64.

This work is licensed under a Сreative Commons Atribiution - NonCommercial 4.0 International (CC BY-NC 4.0)

Khashaev A. A. (Lomonosov Moscow State University (MSU))

Abstract

We consider representations of regular languages over symmetric groups such as finite automata and regular expressions. We show that the problem of computing cardinality of such representations is NP-hard.