Разрешаемые неконтекстно-зависимые языки

15

Можно утверждать, что большинство языков, созданных для описания повседневных проблем, являются контекстно-зависимыми. С другой стороны, возможно и нетрудно найти некоторые языки, которые не являются рекурсивными или даже не рекурсивно-перечислимыми.

Между этими двумя типами находятся рекурсивные, не зависящие от контекста языки. Википедия дает один пример здесь :

Примером рекурсивного языка, который не является контекстно-зависимым, является любой рекурсивный язык, решение которого - сложная задача EXPSPACE, скажем, набор пар эквивалентных регулярных выражений с возведением в степень.

Итак, вопрос: какие существуют другие проблемы, которые разрешимы, но не зависят от контекста? Этот класс задач такой же, как разрешимый EXPSPACE-hard?

Виктор Стафуса
источник
2
Множество (возможно, естественных) проблем верификации (если они решаемы), по крайней мере, PSPACE-завершены. Я не уверен, достаточно ли этого для нечувствительности к контексту, но есть много проблем и с нижней границей EXPSPACE.
Рафаэль

Ответы:

10

CSL такое же , какNSpace(n) (недетерминированная линейное пространство). Любой язык, который находится за пределами , не является CSL.NSpace(n)

Чтобы понять ситуацию, помните, что и даже TQBF.SATNSpace(n)

Какие существуют другие проблемы, которые разрешимы, но не зависят от контекста?

Есть много проблем. Любая задача, которая завершена для класса сложности, большего, чем подойдет (нам нужен P S p a c e, потому что такие задачи, как TQBF в N S p a c e ( n ) , которые завершены для P S p a a с еPSpacePSpaceNSpace(n)PSpaceпотому что сокращение (полиномиальное время) может взорвать размер ввода полиномом). Дать пример будет означать доказательство нижнего предела для класса сложности, содержащего проблему, и это очень и очень сложная задача. Единственный основной способ сделать это - диагонализация, которая интуитивно означает, что более крупный класс должен иметь возможность имитировать меньший класс.

Таким образом , кажется естественное местом , чтобы начать искать естественные примеры языка , которые не являются CSL.ExpSpace-hard

Этот класс задач такой же, как разрешимый EXPSPACE-hard?

Нет. По теореме о пространственной иерархии существуют языки, которые находятся в которых нет в N S p a c e ( n ) . Если вы просите хороших примеров, это будет трудно, потому что теорема работает с использованием диагонализации и, следовательно, язык, который она удовлетворяет этим условиям, является очень искусственным.NSpace(n2)NSpace(n)

Я предлагаю вам задать отдельный вопрос для естественной задачи, которая отделяет от N S p a c e ( n ) .NSpace(n2)NSpace(n)

Кава
источник
2

Точно так же, как зависит от контекста, но не является регулярным, язык L = { a n b n c n : n 0 } разрешим, но не зависит от контекста. Тем не менее, L может быть решен с использованием логарифмического пространства (вам просто нужен счетчик для каждого из символов a , b и c ), поэтому он не является EXSPACE-сложным.{aNбN:N0}Lзнак равно{aNбNсN:N0}Laбс

Кроме того, язык , где r 1 и r 2 являются регулярными выражениями, является PSPACE-полным. Я почти уверен, что это не зависит от контекста, но я не помню доказательств и пишу со своего телефона, так что нелегко искать ссылки.{(р1,р2):L(р1)знак равноL(р2)}р1р2

Janoma
источник
Duh. Сожалею. В конце концов я задал неправильный вопрос! То, что я имею в виду, не было контекстно-зависимым, а не контекстно-свободным. Я изменил вопрос (который, к сожалению, лишает законной силы ваш ответ).
Виктор Стафуса
Кстати, вы можете ответить так, как сейчас?
Виктор Стафуса
@Victor как насчет сейчас?
Яном
Лучше. Но все еще нуждается в улучшении. Лично я немного скептически отношусь к неконтекстуальной чувствительности вашего примера.
Виктор Стафуса
Данная проблема верна, но ее класс ошибочен. Это EXPSPACE-полная, а не PSPACE-полная. Теперь я убежден: en.wikipedia.org/wiki/EXPSPACE
Виктор Стафуса,