Проблема эквивалентности
В теоретической информатике и теории формального языка проблема эквивалентности — это вопрос определения, обозначают ли два представления формальных языков один и тот же формальный язык.
Сложность и разрешимость этой проблемы принятия решений зависят от типа рассматриваемого представления.
Например, в случае конечных автоматов эквивалентность разрешима, и проблема является PSPACE-полной . Кроме того, в случае детерминированных магазинных автоматов эквивалентность разрешима, Жеро Сенизерг выиграл премию Гёделя за этот результат. Впоследствии было показано, что проблема лежит в классе TOWER, наименьшем неэлементарном классе сложности . [1]
Это становится неразрешимой проблемой для автоматов с магазинной памятью или любой машины, которая может определять контекстно-свободные языки или более мощные языки. [2]
Ссылки
- ^ П. Янчар. Эквиваленты систем с опусканием сложны, 2014.
- ^ Дж. Э. Хопкрофт и Дж. Д. Ульман. Введение в теорию автоматов, языки и вычисления , первое издание, 1979.
 | Эта статья по информатике — заглушка . Вы можете помочь Википедии, расширив ее. |
