Entscheidbare nicht kontextsensitive Sprachen

Es ist fraglich, ob die meisten Sprachen, die zur Beschreibung alltäglicher Probleme erstellt wurden, kontextsensitiv sind. Andererseits ist es möglich und nicht schwer, einige Sprachen zu finden, die nicht rekursiv oder sogar nicht rekursiv aufzählbar sind.

Zwischen diesen beiden Typen befinden sich die rekursiven nicht kontextsensitiven Sprachen. Wikipedia gibt ein Beispiel hier :

Ein Beispiel für eine rekursive Sprache, die nicht kontextsensitiv ist, ist jede rekursive Sprache, deren Entscheidung ein EXPSPACE-schwieriges Problem darstellt, beispielsweise die Menge von Paaren äquivalenter regulärer Ausdrücke mit Exponentiation.

Also die Frage: Welche anderen Probleme gibt es, die entscheidbar und doch nicht kontextsensitiv sind? Ist diese Klasse von Problemen dasselbe wie entscheidbares EXPSPACE-hard?

CSL ist dasselbe wie$\mathsf{NSpace}(n)$ (nicht deterministischer linearer Raum). Jede Sprache, die sich außerhalb von befindet, ist keine CSL.$\mathsf{NSpace}(n)$

Um ein Gefühl für die Situation zu bekommen, denken Sie daran, dass und sogar TQBF.$SAT \in \mathsf{NSpace}(n)$

Welche anderen Probleme gibt es, die entschieden werden können, aber dennoch nicht kontextsensitiv sind?

Das sind viele Probleme. Jedes Problem, das für eine Komplexitätsklasse größer als ist, ist erfolgreich (wir benötigen da Probleme wie TQBF in für weil a (Polynomialzeit) Durch Reduzieren kann die Größe einer Eingabe durch ein Polynom in die Luft gesprengt werden. Ein Beispiel zu geben bedeutet, für die Komplexitätsklasse, die das Problem enthält, eine Untergrenze zu beweisen, und das ist eine sehr, sehr schwierige Aufgabe. Der einzige wichtige Weg, den wir bisher kennen, ist die Diagonalisierung, was intuitiv bedeutet, dass die größere Klasse die kleinere Klasse simulieren kann.P S p a c e N S P a c e ( n ) P S P a c $\mathsf{PSpace}$$\mathsf{PSpace}$$\mathsf{NSpace}(n)$$\mathsf{PSpace}$

Daher ein natürlicher Ort zu sein, um nach natürlichen Beispielen für Sprachen zu suchen, die nicht CSL sind.$\mathsf{ExpSpace\text{-}hard}$

Ist diese Klasse von Problemen dasselbe wie entscheidbares EXPSPACE-hard?

No. Durch die Raum - Hierarchie - Theorem gibt es Sprachen , die in sind , die nicht in sind . Wenn Sie nach guten Beispielen fragen, wird dies schwierig, da der Satz mit Diagonalisierung arbeitet und daher die Sprache, die diese Bedingungen erfüllt, sehr künstlich ist.$\mathsf{NSpace}(n^2)$$\mathsf{NSpace}(n)$

Ich schlage vor , dass Sie eine separate Frage für ein natürliches Problem , dass trennt fragen von N S p a c e ( n ) .$\mathsf{NSpace}(n^2)$$\mathsf{NSpace}(n)$

Genau wie kontextfrei, aber nicht regulär ist, ist die Sprache L = { a n b n c n : n ≥ 0 } entscheidbar, aber nicht kontextfrei. Allerdings L gelöst werden kann logarithmischen Raum mit (Sie benötigen nur einen Zähler für jedes der Symbole a , b und c ), so dass es nicht EXSPACE hart ist.$\{a^nb^n:n\geq 0\}$$L=\{a^nb^nc^n:n\geq 0\}$$L$$a$$b$$c$

Auch die Sprache , wobei r 1 und r 2 reguläre Ausdrücke sind, ist PSPACE-vollständig. Ich bin mir fast sicher, dass es nicht kontextsensitiv ist, aber ich kann mich nicht an einen Beweis erinnern, und ich schreibe von meinem Telefon aus, sodass es nicht einfach ist, nach Referenzen zu suchen.$\{(r_1,r_2):L(r_1)=L(r_2)\}$$r_1$$r_2$