RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2021, том 33, выпуск 1, страницы 82–90 (Mi dm1633)

Эта публикация цитируется в 1 статье

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

А. А. Хашаев

МГУ имени М. В. Ломоносова

Аннотация: Рассматриваются автоматы с переходами, помеченными произвольными перестановками. Язык такого автомата состоит из композиций перестановок по всем возможным допустимым цепочкам вычислений. Задача проверки принадлежности для конечных автоматов над симметрическими группами — это задача разрешимости, в которой для данного автомата и перестановки необходимо определить, принадлежит ли перестановка языку автомата. В данной работе показано, что эта задача является NP-полной, а также предложен эффективный алгоритм решения задачи для случая сильно связного автомата.

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

УДК: 519.713

Статья поступила: 19.01.2021

DOI: 10.4213/dm1633


 Англоязычная версия: Discrete Mathematics and Applications, 2022, 32:6, 383–389


© МИАН, 2024