О задаче вычисления мощности регулярного языка над симметрическими группами

Поступила: 26.08.2023

Принята к публикации: 14.01.2024

Дата публикации в журнале: 02.04.2024

Ключевые слова: регулярные языки, конечные автоматы, группы, перестановки, вычислительная сложность

DOI: 10.55959/MSU/0137-0782-15-2024-47-2-58-64

Для цитирования статьи

Хашаев А. А. О задаче вычисления мощности регулярного языка над симметрическими группами // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2024. № 2. С. 58-64 https://doi.org/10.55959/MSU/0137-0782-15-2024-47-2-58-64.

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция-Некоммерчески») 4.0 Всемирная

Хашаев А. А. (Московский государственный университет им. М.В. Ломоносова (МГУ))

Аннотация

Рассматриваются представления регулярных языков над симметрическими группами в виде конечных автоматов и регулярных выражений. В работе доказана NP-трудность задачи проверки мощ- ности языка для таких представлений.