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