Vollständigkeit und kontextsensitive Sprachen.

16

Ich interessiere mich für zwei Fragen bezüglich kontextsensitiver Sprachen (CSL) und Vollständigkeit:

  1. Gibt es einen Begriff von Vollständigkeit für CSL und welche Sprachen sind vollständig?
  2. Gibt es natürliche CSL, die NP-vollständig sind?

Für 2. kann ich mir natürlich NP-vollständige Sprachen vorstellen, die CSL sind (da CSL gleich NSPACE [ ] ist, ist SAT eine CSL), aber ich suche nach dem Gegenteil, dh nach einer kontextbezogenen Sprache. sensible Grammatik , die eine NP-vollständige Sprache beschreibt.n

np-hardness fl.formal-languages space-bounded Michaël Cadilhac
quelle
2
Mal sehen, ob ich (2) richtig verstehe: Wäre es ausreichend, eine kontextsensitive Grammatik zu schreiben, die alle gültigen 3SAT-Instanzen über ein festes Alphabet von Konnektiven und SAT-Variablen generiert?
Evgenij Thorstensen
1
Nun, ich hätte keine SAT-Variablen als Teil des Alphabets hinzugefügt (eine binäre Kodierung ihrer Indizes ist gut genug), aber das würde sicherlich meinen zweiten Punkt beantworten!
Michaël Cadilhac
Übrigens, haben Sie es versucht?
Michaël Cadilhac
4
(1) Wie Sie bereits erwähnt haben, ist es möglich, eine CSG für 3SAT aufzuschreiben. Dies hört sich jedoch ähnlich an, als würde eine vollständige Beschreibung einer Turing-Maschine für das Problem des maximalen Durchflusses (oder eine bestimmte Sprache in P) aufgeschrieben. Ich würde nicht erwarten, dass es einen Einblick in die Komplexitätstheorie geben wird. (Aber hey, wenn sich etwas anderes herausstellt, würde ich mich freuen, es zu hören.) (2) Im Allgemeinen passen der Begriff der kontextsensitiven Grammatik und der Begriff der NP-Vollständigkeit nicht gut zusammen, da die Menge der kontextsensitiven Sprachen werden nicht unter Polynomzeitverkürzungen geschlossen.
Tsuyoshi Ito
1
Vielen Dank für diesen Kommentar Tsuyoshi. In der Tat ist eine Grammatik für 3SAT wahrscheinlich nicht das, wonach ich suche, aber ich bin mit der gleichen Reaktion vorgegangen wie Ihre: Wenn es etwas einfach / natürlich ist, würde ich mich interessieren. Für Ihr (2) ist eines meiner Ziele das Folgende: Angenommen, ich habe eine Klasse von CS-Sprachen, die durch die Reduzierung des Protokollbereichs geschlossen wurde, und ich möchte zeigen, dass meine Klasse keine NP-vollständigen Probleme enthält (oder wahrscheinlich nicht enthält). Ich müsste nur zeigen, dass die spezifische NP-vollständige CS-Sprache nicht in meiner Klasse ist, was einfacher sein könnte, wenn die Sprache natürlich CS ist.
Michaël Cadilhac

Antworten:

9

Um Ihre erste Frage zu beantworten, ist eine Reduzierbarkeit, die Ihren Anforderungen entspricht, die log-lin-Reduzierbarkeit. Dies ist die log-space-Reduzierbarkeit mit der zusätzlichen Einschränkung, dass die Größe der Ausgabezeichenfolge der Reduzierung höchstens linear zur Größe der Eingabe ist. Wenn ich mich richtig erinnere, ist das Mitgliedschaftsproblem für kontextsensitive Grammatiken (oder, wenn Sie möchten, für linear begrenzte Automaten) das kanonische CSL-vollständige Problem bezüglich der Protokollreduzierbarkeit.

Auf der angewandten Seite ist das Universalitätsproblem (gewöhnlicher) regulärer Ausdrücke über binäres Alphabet die CSL-vollständige Wrt-Log-Lin-Reduzierbarkeit. Der Begriff und das Vollständigkeitsergebnis finden sich bei Albert R. Meyer und Larry J. Stockmeyer (SWAT 1972) auch: Stockmeyer (Doktorarbeit, MIT 1974). Zu weiteren Hintergründen und ähnlichen Ergebnissen in diesem Bereich siehe auch die aktuelle Umfrage von Holzer und Kutrib (DLT 2010).

BEARBEITEN (06.03.2017): In Bezug auf Ihre zweite Frage zitiert die akzeptierte Antwort auf die folgende Frage eine Abhandlung von Rounds (1973), die einen in eine Richtung verschachtelten Stapelautomaten konstruiert, der SAT erkennt. Obwohl SAT nicht als "natürliches" CSL eingestuft wird, kann es sich lohnen, in der Literatur nach anderen Beispielen für in einer Richtung verschachtelte Stapelautomaten oder indizierte Grammatiken zu suchen.

Kontextsensitive Grammatik für SAT?

Hermann Gruber
quelle
Vielen Dank, das ist in der Tat, wonach ich gesucht habe!
Michaël Cadilhac
Für die Bearbeitung: Fantastisch! Vielen Dank, dass Sie dorthin zurückgekehrt sind und diese Antwort vervollständigt haben.
Michaël Cadilhac