Können Multipebble-Automaten alle deterministischen kontextsensitiven Sprachen bestimmen?

Ein MPA (Multipebble-Automat) ist ein 2DFA (bidirektionaler deterministischer endlicher Automat), der eine beliebige Anzahl von Steinen verwenden kann (tatsächlich höchstens Steine auf einer gegebenen Eingabe - die Eingabe wird auf das Band zwischen zwei Enden geschrieben -Markierungen als ). Während der Berechnung kann ein MPA erkennen, ob das Symbol unter dem Kopf einen Kiesel aufweist, und er kann dann einen Kiesel platzieren (den Kiesel entfernen), wenn kein Kiesel vorhanden ist (ein Kiesel). $|w|+2$ $w$ $\# w \#$

ist ein Homomorphismus, wobei ein Symbol ist und . $h_k(\sigma) = \underbrace{\sigma \cdots \sigma}_{k \mbox{ times}} = \sigma^k$ $\sigma$ $k>0$

Für jede deterministische kontextsensitive Sprache es nicht schwer zu zeigen, dass es ein so dass $\mathtt{L} ~~ \left( \mathtt{L} \in \mathsf{DSPACE(n)} \right),$ $k>0~$ $h_k( \mathtt{L} )$ von einem MPA erkannt werden kann. Also können wir das sagen

Jedes "Problem", das von einem linearen DTM (deterministische Turing-Maschine) entschieden werden kann, kann von einem MPA entschieden werden.

Ist es auch wahr für jede Sprache in ? Können MPAs alle deterministischen kontextsensitiven Sprachen bestimmen? $\mathsf{DSPACE(n)}$

ist die Länge von . $|w|$ $w$

ist das Symbol von , wobei. $w_i$ $i^{th}$ $w$ $1 \leq i \leq |w|$

. $h_k(\mathtt{L}) = \left\lbrace h_k(w_1) h_k(w_2) \cdots h_k(w_{|w|}) \mid w \in \mathtt{L} \right\rbrace$

cc.complexity-theory reference-request automata-theory space-bounded Abuzer Yakaryilmaz
quelle

interessante Frage; beabsichtigen, einige lose verwandte Verweise zu veröffentlichen, die relevant sein könnten, wenn sich niemand anderes etwas Besseres / Näheres einfallen lässt. eine Frage. CSLs in DSpace (n) müssen nicht mit allen linearen DTMs identisch sein, oder? eigentlich ist das eine offene frage oder? oder eng mit einem verwandt? weil CSLs nachweislich NSpace (n) entsprechen und offen sind, wenn NSpace (n) == DSpace (n).

vzn

@vzn: CSLs in DSPACE (n) werden deterministische CSLs genannt und bilden genau DSPACE (n).

Abuzer Yakaryilmaz

in Ordnung. Der Hinweis, den ich als "wahrscheinlich verwandt" in Erinnerung hatte, sind die Kieselargumente, die verwendet wurden, um die Frage DTime (n ^ k) =? Ntime (n ^ k) anzugreifen, z. B. die jüngsten Ergebnisse von Santhanam , die auf dem PPST-Ergebnis aufbauen. Ein weiteres Problem, von dem ich intuitiv denke, dass es damit zusammenhängt, ist das Problem der Komprimierung einer TM-

Laufsequenz

kannst du die frage bitte etwas klären? Haben Sie nicht gerade in dem hervorgehobenen Text behauptet, dass MPAs alle deterministischen CSLs bestimmen können? Gibt es beispielsweise eine Möglichkeit, Ihre Frage in Bezug auf h_k (L) umzuformulieren?

vzn

Das Theorem besagt, dass wenn

eine DCSL ist, es einige

so dass

durch eine MPA berechnet werden kann. Die Frage ist, können wir

σ

$\sigma$

k

$k$

h_{k} (σ)

$h_k(\sigma)$

k = 1

$k=1$

Ben Standeven

Antworten:

Vielleicht können Sie in DPSACE (n) eine Sprache erstellen, die von einem MPA mit mit einem Diagonalisierungsargument erkannt werden kann (wahrscheinlich ähnelt die Idee der in Bens Antwort, aber ich habe mich nicht damit befasst): $k=1$

Angenommen, Sie codieren über dem Alphabet einen MPA mit einer Liste von Übergängen: $\Sigma = \{0,1\}$

$s,a,p \rightarrow s',p',L|R;...\#$

wobei der aktuelle Zustand ist, das aktuelle Symbol ist, der Kieselzustand ist, der neue Zustand ist, der neue Kieselzustand ist, ist die Bewegungsrichtung, ist ein Endmarker). $s$ $a$ $p$ $s'$ $p'$ $L|R$ $\#$

Eine Turingmaschine am Eingang kann prüfen, ob es sich um eine gültige Beschreibung eines und diese am Eingang für simulieren Schritte mit Zellen, dehnen die Eingabe auf diese Weise: $M$ $x$ $MPA_x$ $x$ $4^{|x|}$ $6|x|+\log|x|$

 MPA description # MPA tape # curr_state # counter #

Wo:

Die MPA-Beschreibung ist die ursprüngliche Eingabezeichenfolge (hat die Länge ); $x$ $|x|$
MPA-Band ist die MPA-Banddarstellung: Für jede Zelle können wir 3 Bits verwenden, um das Kopf-Flag, das Kiesel-Flag und den (festen) Bandinhalt zu speichern (hat die Länge ); $3|x|$
curr_state speichert den aktuellen Zustand des MPA (hat die Länge ); $\log |x|$
counter ist der Simulationsschrittzähler, der nach jedem Simulationsschritt aktualisiert wird (Länge ). $2|x|$

Wenn in anhält Schritte, dann gibt TM das Gegenteil aus (wenn es nicht anhält, gibt 0 aus). $MPA_x$ $4^{|x|}$ $M$ $M$

Für groß genug ist die Simulationsschritte sind größer als die größer ist als die Länge einer vollständigen Konfigurationsbeschreibung von ; auf diese Weise, wenn in nicht anhält Schritte, dann sind wir sicher, dass es für immer Schleife wird. $x > x_0$ $4^{|x|}$ $2^{|x|+2} |x| \log |x|$ $MPA_x$ $MPA_x$ $4^{|x|}$

Angenommen, es gibt ein , das die gleiche Sprache von , dann hält es immer an, und Sie können ein "größeres" aufbauen das die gleiche Sprache entscheidet, mit (addieren Sie einfach Dum Staaten). $MPA_y$ $L$ $M$ $MPA_{y'}$ $y'>x_0$

Konstruktionsbedingt gilt was ein Widerspruch ist. $MPA_{y'}(y') = 1 - M(y') = 1 - MPA_{y'}(y')$

Marzio De Biasi
quelle

Ja, das ist das Argument, an das ich gedacht habe.

Ben Standeven

Gegenbeispiel: Das Halteproblem für MPAs ist im linearen Raum entscheidbar: Wenn der MPA N Zustände hat, benötigen wir | k | +2 Bits Platz zum Speichern der Kieselorte, log N Bits zum Speichern des aktuellen Zustands und Bits zum Speichern eines Zählers; Wenn der Zähler zyklisch läuft, wird die simulierte Maschine niemals anhalten. Dies ist linear in | k | (Ignorieren Sie den O (N \ log N) Speicherplatz, der zur Beschreibung der Maschine erforderlich ist), wie erforderlich. $\log(N(|k|+2))+|k|+2$

Da diese Sprache im linearen Raum entscheidbar ist, kann sie auch als DCSL ausgedrückt werden.

Ben Standeven
quelle

Vielleicht fehlen mir einige einfache Punkte, aber ich konnte nicht verstehen, wie Ihr Gegenbeispiel funktioniert. Könnten Sie bitte genauer beschreiben, wie Ihre Argumentation funktioniert? Vielen Dank!!!

Abuzer Yakaryilmaz