Проблема непустоты пересечения
Проблема непустоты пересечения , также известная как проблема пересечения конечных автоматов. [1] или проблема непустоты пересечения , представляет собой PSPACE-полную решающую задачу из области теории автоматов .
Определения
[ редактировать ]Проблема решения непустоты определяется следующим образом. Учитывая автомат в качестве входных данных, цель состоит в том, чтобы определить, является ли язык автомата непустым. Другими словами, цель состоит в том, чтобы определить, существует ли строка, которую принимает автомат.
Проблемы непустоты изучаются в области теории автоматов уже много лет. Было показано, что несколько распространенных проблем непустоты являются полными для классов сложности от детерминированного логического пространства до PSPACE . [2]
непустоты пересечения Проблема решения связана с тем, является ли пересечение данных языков непустым. В частности, проблема непустоты пересечения определяется следующим образом. Учитывая список детерминированных конечных автоматов в качестве входных данных, цель состоит в том, чтобы определить, имеют ли связанные с ними регулярные языки непустое пересечение. В другом случае цель состоит в том, чтобы определить, существует ли строка, которая принимается всеми автоматами в списке.
Алгоритм
[ редактировать ]Существует общий алгоритм экспоненциального времени , который решает проблему непустоты пересечения, основанную на конструкции декартова произведения, введенной Майклом О. Рабином и Даной Скотт . [3] Идея состоит в том, что все автоматы вместе образуют автомат-продукт, так что строка принимается всеми автоматами тогда и только тогда, когда она принимается автоматом-продуктом. Следовательно, поиск в ширину (или поиск в глубину ) на диаграмме состояний автомата продукта определит, существует ли путь от начального состояния продукта к одному из конечных состояний продукта. Существует ли такой путь или нет, это эквивалентно определению того, принимается ли какая-либо строка всеми автоматами в списке.
Примечание. Автомат продукта не обязательно создавать полностью. Вместе автоматы предоставляют достаточную информацию, чтобы при необходимости можно было определить переходы.
Твердость
[ редактировать ]Проблема непустоты пересечения была PSPACE-полной в работе Декстера Козена в 1977 году. [1] С тех пор было показано множество дополнительных результатов по твердости. Тем не менее, вопрос о том, существуют ли более быстрые алгоритмы, по-прежнему остается открытой. [4]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Козен, Д. (1977). Нижние оценки для систем естественных доказательств . Учеб. 18-й Симп. по основам информатики. IEEE. стр. 254–266. дои : 10.1109/SFCS.1977.16 .
- ^ Галил, Цви (1976). «Иерархии полных задач» . Акта Информатика . 6 (1). Спрингер-Верлаг: 77–88. дои : 10.1007/BF00263744 . S2CID 26562214 .
- ^ Рабин, Миссури; Скотт, Д. (1959). «Конечные автоматы и проблемы их решения» . IBM J. Res. Дев . 2 (3). Корпорация IBM: 114–125. дои : 10.1147/рд.32.0114 .
- ^ «О пересечении конечных автоматов» . rjlipton.wordpress.com . Проверено 15 декабря 2020 г.
* Неполный список публикаций по теме см. здесь .