Rechenleistung deterministischer versus nichtdeterministischer Min-Heap-Automaten

15

Dies ist eine Folgefrage von diesem .

In einer früheren Frage zu exotischen Zustandsautomaten haben sich Alex ten Brink und Raphael mit den Rechenfähigkeiten einer besonderen Art von Zustandsautomaten befasst: Min-Heap-Automaten. Sie konnten zeigen, dass die Menge der von solchen Maschinen akzeptierten Sprachen ( ) weder eine Teilmenge noch eine Obermenge der Menge der kontextfreien Sprachen ist. In Anbetracht der erfolgreichen Lösung und des offensichtlichen Interesses an dieser Frage stelle ich weiterhin mehrere Anschlussfragen.HAL

Es ist bekannt, dass deterministische und nicht deterministische endliche Automaten äquivalente Rechenfähigkeiten haben, ebenso wie deterministische und nicht deterministische Turingmaschinen. Die Rechenfähigkeiten deterministischer Push-Down-Automaten sind jedoch geringer als die nicht deterministischer Push-Down-Automaten.

Sind die Rechenfähigkeiten deterministischer Min-Heap-Automaten geringer oder gleich denen nicht deterministischer Min-Heap-Automaten?

Patrick87
quelle

Antworten:

3

Es scheint, dass für dieses Modell nicht deterministische Maschinen nicht deterministischen Maschinen entsprechen, und zwar aus dem gleichen Grund, aus dem deterministische PDAs nicht nicht deterministischen Maschinen entsprechen.

Betrachten Sie die Sprache

L=x$y|x|=|y|xy
(wobei ein Sonderzeichen ist, das nicht in x und y enthalten ist ).$xy

I behaupten , dass eine nicht deterministische Maschine - H A L diese Sprache entscheiden kann: Es ist der gleiche wie der PDA für führt L . Die Standard-PDA-Lösung verwendet den Stapel nur zum Zählen von Offsets: Sie errät nicht deterministisch einen Offset i , merkt sich den Wert von x i (fügt dem Stapel bei jedem Schritt ein Symbol hinzu), und der PDA ignoriert die Eingabe, bis er das $ und findet Dann werden die Symbole aus dem Stapel entfernt, bis sie leer sind. Zu diesem Zeitpunkt sind wir genau bei y i und der PDA kann prüfen, ob x iy i istNHEINLLichxich$yichxichyich. (Wenn in der Mitte etwas schief geht, "stirbt" der PDA). Da das Stapelalphabet unär ist, kann es mit einer Min-Heap-Maschine simuliert werden. Tatsächlich: Jedes , das von einem PDA mit einem unären Alphabet akzeptiert wird, kann von einer Min-Heap-Maschine akzeptiert werden. (Ich ignoriere möglicherweise ein anderes Sonderzeichen, das hinzugefügt wurde, um einen leeren Stapel zu identifizieren, aber dem Haufen kann ein gleichwertiges Zeichen hinzugefügt werden.)L

Für die andere Richtung habe ich keinen formalen Beweis, aber hier sind meine Gedanken:

Ich behaupte, dass eine deterministische Maschine - H A L nicht in der Lage ist, diese Sprache zu bestimmen. Intuitiv kann der Inhalt des Heaps nicht mit x korreliert werden (andernfalls permute x . Der Inhalt des Heaps bleibt derselbe.). Dies deutet darauf hin , dass einzige , was zählt die Anzahl der Elemente in dem Heap ist, aber dann, wenn D - H A L entscheiden kann , L , kann so eine deterministic- P D A .DHEINLxxDHEINLLPDEIN

Bearbeiten: Weitere Details zum Anspruch "permute ". Unter der Annahme, dass Raffaels Vermutung existiert, ist x 1 und x 2, dass nach dem Lesen der Inhalt des Haufens der gleiche ist. Betrachten Sie dann die Wörter x 1 $ x 1 und x 2 $ x 1 . Der Inhalt des Heaps ist der gleiche, wenn der HAL das Dollarzeichen erreicht, daher muss er entweder beide akzeptieren oder beide ablehnen. widerspruch .xx1x2x1$x1x2$x1

sieht jemand einen sofortigen Beweis für die Vermutung?

Ran G.
quelle
x
Welche Definition von Min-Heaps verwenden Sie: meine ursprüngliche oder die natürlichere, die Raphael vorgeschlagen hat? Können Sie in beiden Fällen klarer sagen, wie eine nicht deterministische Maschine die von Ihnen angegebene Sprache akzeptieren würde ... was wird auf den Haufen gelegt und wann wird sie entfernt?
Patrick87
nn