Ermitteln der Funktionen eines Min-Heap-Automaten (oder eines anderen exotischen Automaten)

Am Ende dieses Beitrags finden Sie Erläuterungen zu den Definitionen von Min-Heap-Automaten.

Man kann sich vorstellen, eine Vielzahl von Datenstrukturen zum Speichern von Informationen zur Verwendung durch Zustandsautomaten zu verwenden. Zum Beispiel speichern Push-Down-Automaten Informationen in einem Stapel, und Turing-Maschinen verwenden ein Band. Es hat sich gezeigt, dass Zustandsmaschinen, die Warteschlangen verwenden, und solche, die zwei Mehrfachstapel oder -bänder verwenden, in der Leistung Turing-Maschinen gleichwertig sind.

Stellen Sie sich eine Min-Heap-Maschine vor. Es funktioniert genau wie ein Push-Down-Automat, mit folgenden Ausnahmen:

1. Anstatt sich das letzte Element anzusehen, das Sie dem Heap hinzugefügt haben, sehen Sie sich nur das kleinste Element (mit der auf der Grundlage der Maschine definierten Reihenfolge) an, das sich derzeit auf dem Heap befindet.
2. Anstatt das letzte Element zu entfernen, das Sie dem Heap hinzugefügt haben, können Sie nur eines der kleinsten Elemente (mit der auf Maschinenbasis definierten Reihenfolge) entfernen, die sich derzeit auf dem Heap befinden.
3. Anstatt ein Element oben auf dem Heap hinzuzufügen, können Sie dem Heap nur ein Element hinzufügen, dessen Position anhand der anderen Elemente im Heap bestimmt wird (wobei die Reihenfolge für jeden Computer festgelegt wird).

Dieser Computer kann alle regulären Sprachen akzeptieren, indem er den Heap nicht verwendet. Es kann auch die Sprache akzeptieren, indem dem Heap 's hinzugefügt wird. und Entfernen von 's aus dem Haufen, wenn es ' s liest . Es kann eine Vielzahl anderer kontextfreier Sprachen akzeptieren. Es kann jedoch beispielsweise nicht (ohne Beweis angegeben) akzeptieren . EDIT: oder kann es? Ich glaube nicht, dass es das kann, aber ich war schon einmal überrascht, und ich bin mir sicher, dass ich immer wieder überrascht sein werde, wenn ich meine Vermutungen habe, dass ich weiterhin ein ... naja aus mir mache.$\displaystyle \{a^{n}b^{n} \in \{a, b\}^{*} \mid n \ge 0\}$$a$$a$$b$$\displaystyle \{w \in \{a, b\}^{*} \mid w = w^{R}\}$

Kann es alle kontextsensitiven oder Turing-vollständigen Sprachen akzeptieren?

Welche Forschungsarbeiten wurden allgemein in dieser Richtung durchgeführt? Welche Ergebnisse gibt es, wenn überhaupt? Ich interessiere mich auch für andere Arten von exotischen Zustandsautomaten, möglicherweise für solche, die andere Datenstrukturen für die Speicherung verwenden, oder für verschiedene Arten von Zugriffsbeschränkungen (z. B. wie LBAs eingeschränkte TMs sind). Referenzen sind willkommen. Ich entschuldige mich im Voraus, wenn diese Frage Unwissenheit zeigt.

Formale Definition:

Ich stelle hier einige detailliertere Definitionen von Min-Heap-Automaten zur Verfügung, um die weitere Diskussion bei Fragen zu klären, die auf dieses Material verweisen.

Wir definieren einen nicht deterministischen Min-Heap-Automaten vom Typ 1 als ein 7-Tupel wobei ...

1. $Q$ ist eine endliche, nicht leere Menge von Zuständen;
2. $q_0 \in Q$ ist der Anfangszustand;
3. $A \subseteq Q$ ist die Menge der akzeptierenden Zustände;
4. $\Sigma$ ist ein endliches, nicht leeres Eingabealphabet.
5. γ ∈ & Ggr; w ( γ ) ∈ N w ( γ 1 ) = w ( γ 2$\Gamma$ ist ein endliches, nicht leeres Eingabealphabet, bei dem die Gewichtung eines Symbols , ist, dass ;$\gamma \in \Gamma$$w(\gamma) \in \mathbb{N}$$w(\gamma_1) = w(\gamma_2) \iff \gamma_1 = \gamma_2$
6. $Z_0 \notin \Gamma$ ist das spezielle Heap-Symbol;
7. $\delta : Q \times (\Sigma \cup \{\epsilon\}) \times (\Gamma \cup \{Z_0\}) \rightarrow \mathcal{P}({Q \times \Gamma^*})$ ist die Übergangsfunktion.

Die Übergangsfunktion geht von einem anfänglich leeren Heap aus, der nur aus . Die Übergangsfunktion kann dem Heap eine beliebige Sammlung (endlich, aber möglicherweise leer oder mit Wiederholungen) von Elementen . Alternativ kann die Übergangsfunktion eine Instanz des Elements mit der niedrigsten Gewichtung aller auf dem Heap verbleibenden Elemente (dh des Elements auf dem Heap) entfernen . Die Übergangsfunktion kann nur die oberste (dh mit minimaler Gewichtung) Symbolinstanz zum Bestimmen eines gegebenen Übergangs verwenden.γ 1 , & ggr; 2 , . . . , γ k ∈ Γ γ w ( γ $Z_0$$\gamma_1, \gamma_2, ..., \gamma_k \in \Gamma$$\gamma$$w(\gamma)$

Ferner ist eine Definition des Typs 1 determinis min-heap Automat ein Typ-1 nondeterministic min-heap Automaten zu sein , die erfüllt die folgende Eigenschaft: für alle Strings , so dass und , .| x | = n σ ∈ Σ | δ n + 1 ( q 0 , x σ y , Z 0 ) | ≤ $x{\sigma}y \in \Sigma$$|x| = n$$\sigma \in \Sigma$$|\delta^{n+1}(q_0, x{\sigma}y, Z_0)| \leq 1$

Definieren Sie auch einen nicht deterministischen Min-Heap-Automaten des Typs 2 genau wie einen nicht deterministischen Min-Heap-Automaten des Typs 1, mit Ausnahme der folgenden Änderungen:

1. γ ∈ & Ggr; w ( γ ) ∈ N w ( γ 1 ) = w ( γ 2 ) γ 1 = γ $\Gamma$ ist ein endliches, nicht leeres Eingabealphabet, bei dem die Gewichtung eines Symbols , ist, dass impliziert nicht unbedingt ; Mit anderen Worten, verschiedene Heap-Symbole können dasselbe Gewicht haben.$\gamma \in \Gamma$$w(\gamma) \in \mathbb{N}$$w(\gamma_1) = w(\gamma_2)$$\gamma_1 = \gamma_2$
2. Wenn Instanzen unterschiedlicher Heap-Symbole mit derselben Gewichtung zum Heap hinzugefügt werden, wird ihre relative Reihenfolge gemäß einer stapelartigen Last-In-, First-Out- (LIFO-) Reihenfolge beibehalten.

Vielen Dank an Raphael, der auf diese natürlichere Definition hingewiesen hat, die die kontextfreien Sprachen erfasst (und erweitert).

Einige Ergebnisse zeigten bisher:

1. Typ-1-Min-Heap-Automaten erkennen eine Menge von Sprachen, die weder eine Teilmenge noch eine Obermenge der kontextfreien Sprachen ist. [ 1 , 2 ]
2. Typ-2-Min-Heap-Automaten erkennen nach ihrer Definition einen Satz von Sprachen, der eine angemessene Obermenge der kontextfreien Sprachen darstellt, sowie eine angemessene Obermenge der Sprachen, die von Typ-1-Min-Heap-Automaten akzeptiert werden.
3. Sprachen, die von Typ-1-Min-Heap-Automaten akzeptiert werden, scheinen unter Vereinigung, Verkettung und Kleene-Stern geschlossen zu sein, jedoch nicht unter Komplementierung [ 1 ], Schnittmenge oder Differenz.
4. Sprachen, die von nicht deterministischen Min-Heap-Automaten des Typs 1 akzeptiert werden, scheinen eine angemessene Obermenge von Sprachen zu sein, die von deterministischen Min-Heap-Automaten des Typs 1 akzeptiert werden.

Es kann ein paar andere Ergebnisse geben, die ich verpasst habe. Weitere Ergebnisse sind (möglicherweise) in Vorbereitung.

Folgefragen

1. Schließung unter Umkehrung? - Öffnen Sie
2. Abschluss unter Ergänzung? -- Nein!
3. Steigert Nichtdeterminismus die Macht? -- Ja?
4. Ist für Typ 2? $HAL \subsetneq CSL$- Öffnen Sie
5. Erhöht das Hinzufügen von Heaps die Leistung für Typ 1? - für (?) k > $HAL^1 \subsetneq HAL^2 = HAL^k$$k > 2$
6. Erhöht das Hinzufügen eines Stapels die Leistung für Typ 1? - Öffnen Sie

Sie können die kanonische nicht kontextfreie (aber kontextsensitive) Sprache mit diesem Typ von Zustandsmaschine erkennen. Der springende Punkt ist , dass Sie Token zu dem Heap für jeden addieren Charakter, und während die Parsen Zeichen, die Sie hinzufügen ‚größer‘ Token zu dem Haufen, so dass sie nur am unteren Rand des Haufens am Ende , wenn Sie alle analysiert haben Figuren.a b $\{ a^n b^n c^n\ |\ n \geq 1 \}$$a$$b$$b$

Heap-Symbole sind und , wobei . Wir verbrauchen alle Symbole in der Eingabe und fügen dem Heap Symbol hinzu. Wenn wir auf ein stoßen , wechseln wir die Strategie: Für jedes wir später stoßen, entfernen wir ein aus dem Haufen und fügen dem Haufen ein . Wenn wir auf ein stoßen , sollten wir s mehr haben, um es zu entfernen, und dann entfernen wir für jedes in der verbleibenden Eingabe ein aus dem Heap. Wenn der Heap am Ende leer ist, ist die Zeichenfolge in der Sprache. Natürlich lehnen wir ab, wenn etwas schief geht.b a < b ein a b b ein b c ein c $a$$b$$a < b$$a$$a$$b$$b$$a$$b$$c$$a$$c$$b$

Aktualisieren:

Die Sprache kann von Min-Heap-Automaten nicht erkannt werden. Angenommen, wir haben einen Min-Heap-Automaten, der erkennt . Wir schauen uns den 'Zustand' an, in dem sich der Automat befindet, nachdem wir gelesen haben (der erste Teil der Eingabe, also ist nächste). Der einzige Zustand, den wir haben, ist der Inhalt des Heaps und der spezielle Zustand des Automaten, in dem er sich befindet. Dies bedeutet, dass dieser 'Zustand' nach dem Erkennen von genügend Informationen enthalten muss, um mit .$EPAL = \{ ww^R | w \in \{a, b\}^* \}$$EPAL$$w$$w^R$$w$$w^R$

Dazu müssen insbesondere verschiedene Zustände vorhanden sein (wobei ), da es mögliche Wörter gibt, die aus und Zeichen bestehen. Da es nur eine begrenzte Anzahl von Zuständen und nur eine begrenzte Anzahl von Heap-Zeichen gibt, impliziert dies, dass ein Wort für das der Heap eine exponentielle Anzahl von Heap-Zeichen enthält, z . B. .$2^n$$n = |w|$$2^n$$a$$b$$w$$x$

Wir beweisen zunächst den Satz für deterministische Min-Heap-Automaten und erweitern diesen Beweis dann auf nicht deterministische Min-Heap-Automaten. Insbesondere deterministische Automaten, die eine Sprache erkennen, befinden sich nicht in einer Endlosschleife, was eine nützliche Eigenschaft ist.

Wir werden beweisen, dass der Heap höchstens eine Anzahl von Heap-Token enthalten kann, die in der Anzahl der von der Eingabe gelesenen Zeichen linear ist. Dies schließt sofort aus, dass auf dem Heap exponentiell oft vorkommt, was den Beweis vervollständigt, dass von Min-Heap-Automaten nicht erkannt werden kann.$x$$EPAL$

Da sich in unserem Automaten nur eine endliche Anzahl von Zuständen befindet und sich ein deterministischer Automat nicht in eine Endlosschleife einfügt, fügt er beim Lesen eines Eingangssignals dem Heap höchstens eine konstante Anzahl von Heap-Zeichen hinzu. In ähnlicher Weise kann beim Konsumieren eines Heap-Symbols höchstens eine konstante Anzahl von Heap-Zeichen hinzugefügt werden, die streng größer als und es kann nur die Anzahl von Symbolen auf dem Stapel verringert werden (andernfalls erhalten wir eine Endlosschleife).$y$$y$$y$

Das Verbrauchen von Heap-Symbolen kann daher zu einem (enormen) Aufbau größerer Heap-Symbole führen. Da es jedoch nur eine konstante Anzahl verschiedener Arten von Heap-Symbolen gibt, ist dies nur eine konstante Anzahl, die nicht von abhängig ist . Dies impliziert, dass die Anzahl der Heap-Symbole höchstens einige (große) Konstanten multipliziert mit der Anzahl der bisher gelesenen Eingabesymbole beträgt. Damit ist der Beweis für den deterministischen Fall abgeschlossen.$n$

Im nicht deterministischen Fall ist der Beweis ähnlich, aber etwas kniffliger: Anstatt dem Heap höchstens eine konstante Anzahl von Heap-Token hinzuzufügen, wird dem Heap eine beliebige Anzahl von Heap-Token hinzugefügt. Entscheidend ist jedoch, dass diese Anzahl nicht von abhängt . Insbesondere, wenn wir nicht deterministisch genau die richtigen Heap-Symbole auf dem Heap nach dem Erkennen von (Recht zum Erkennen von ), können wir auch nicht deterministisch die Heap-Symbole auswählen, die mit einem anderen Wort übereinstimmen , und damit erkennen und widersprechen damit, dass der Min-Heap-Automat genau erkennt .$n$$w$$w^R$$w'$$w w'^R$$EPAL$

Update 3: Ich werde das letzte Argument (über Nicht-Determinismus) rigoros machen. Durch das obige Argument muss eine unendliche Menge von Wörternso dass für jedesnach dem Erkennen vonder HeapElemente enthält ( Beachten Sie, dass wir übersprechen können,da wir eine unendliche Menge von Wörtern haben. Da wir nicht so viele Elemente mit deterministischen Mitteln auf den Heap bekommen können, müssen wir eine Art Schleife haben, in der wir uns zunächst nicht deterministisch entschieden haben, dem Heap weitere Elemente hinzuzufügen (ohne Eingaben zu verbrauchen) und diese später zu beenden Schleife, und wir müssen diese Schleifemaldurchlaufen haben.$W \subseteq \{a,b\}^*$$w \in W$$w$$\omega(|w|)$$O(f(|w|))$$\omega(1)$

Nehmen Sie die Menge aller von verwendeten Schleifen . Da es nur -Zustände gibt, ist die Größe dieser Menge , und die Menge aller ihrer Teilmengen ist auch . Man beachte nun, dass der "deterministische" Teil der Ausführungspfade nur zu der Token beitragen kann , was bedeutet, dass viele der exponentiellen Anzahl verschiedener Wörter Ausführungspfade haben müssen, deren "deterministische" Teile die gleichen Beiträge leisten Jetons auf den Haufen. Insbesondere ist der einzige Weg, mehr Token zu erhalten, die oben identifizierten Schleifen zu nehmen.$W$$O(1)$$O(1)$$O(1)$$O(|w|)$

Kombiniert man diese Beobachtungen, bedeutet dies, dass es in , und , zwei unterschiedliche Wörter geben muss, deren "deterministischer" Teil der Ausführungspfade die gleichen Token zum Heap beiträgt und die sich durch die Aufnahme einer Teilmenge der obigen Schleifen unterscheiden unterschiedlich oft, aber mit derselben Teilmenge von Schleifen (denken Sie daran, dass nur dieser Schleifen vorhanden sind).$W$$w_1$$w_2$$O(1)$

Wir können nun zeigen, dass auch vom Min-Heap-Automaten erkannt werden kann: Wir folgen dem Ausführungspfad für wie oben, aber wir durchlaufen die Schleifen genauso oft, wie der Ausführungspfad für durchläuft. Dies füllt den Min-Heap mit Token, so dass als Suffix akzeptiert wird, wodurch der Beweis abgeschlossen wird.$w_1 w_2$$w_1$$w_2$$w_2$

Update 2:

Mir ist gerade aufgefallen, dass das oben Genannte bedeutet, dass wir einen deterministischen Min-Heap-Automaten simulieren können, indem wir nur logarithmischen Raum verwenden: Wir behalten einen Zähler für jede Art von Zeichen im Min-Heap. Wie oben gezeigt, ist dieser Zähler höchstens und kann daher nur mit gespeichert werden (da es nur eine konstante Anzahl dieser Zähler gibt). Das gibt uns:O ( log n $O(n)$$O(\log n)$

$\mathrm{DHAL} \subset \mathrm{L}$

$\mathrm{HAL} \subset \mathrm{NL}$

Dabei ist die Menge der Sprachen, die von einem deterministischen Min-Heap-Automaten erkannt werden.$\mathrm{DHAL}$

Folgendes wissen wir:

• $\mathrm{HAL} \setminus \mathrm{CFL} \neq \emptyset$ (Typ 1, Typ 2)
• $\mathrm{CFL} \setminus \mathrm{HAL} \neq \emptyset$ (Typ 1)
• $\mathrm{CFL} \subseteq \mathrm{HAL}$ (per Definition Typ 2)
• $\mathrm{CSL} \setminus \mathrm{HAL} \neq \emptyset$ (Typ 1, Typ 2)

Einzelheiten und einige andere Hinweise finden Sie weiter unten.

$\mathrm{HAL} \setminus \mathrm{CFL} \neq \emptyset$

Dieser Teil der Antwort bezieht sich sowohl auf Typ 1 als auch auf Typ 2.

Ein Min-Heap-Automat (HA) mit endlichem, vollständig geordnetem Heap-Alphabet akzeptiert .$L = \{ a^nb^nc^n \mid n \in \mathbb{N} \} \in \mathrm{CSL} \setminus \mathrm{CFL}$

Annahmen: Ähnlich wie bei einem PDA verbraucht unsere Übergangsfunktion das oberste Heap-Symbol und schreibt eine beliebige Anzahl von Heap-Symbolen zurück. Der Heap enthält anfangs ein definiertes Symbol das größer ist als alle anderen Heap-Symbole.$\$$

Sei ein Min-Heap-Automat mit$A = (Q,\Sigma_I, \Sigma_H, \rightarrow, q_0, Q_F)$

• $Q = \{q_0, q_1, q_2, q_f\}$ die Menge von Zuständen
• $\Sigma_I = \{a,b,c\}$ das Eingabealphabet.
• $\Sigma_H = {a,b,\$}$ das Heap-Alphabet mit der Reihenfolge .$a \lt b \lt \$$
• $Q_F = \{q_f\}$
• $\rightarrow\ \subseteq (Q \times \Sigma_I \times \Sigma_H) \times (Q \times \Sigma_H^*)$ mit
  • $(q_0,a,\sigma) \rightarrow (q_0, a\sigma)$ für all$\sigma \in \Sigma_H$
  • $(q_0,b,a) \rightarrow (q_1,b)$
  • $(q_1,b,a) \rightarrow (q_1,b)$
  • $(q_1,c,b) \rightarrow (q_2,\varepsilon)$
  • $(q_2,c,b) \rightarrow (q_2, \varepsilon)$
  • $(q_2,c,\$) \rightarrow (q_f, \varepsilon)$

Der Automat schreibt für jedes in der Eingabe ein in den Heap . Wenn ein auftritt, verbraucht es so viele wie es , und schreibt für jedes gefundene ein auf den Heap . Dies gilt nicht disturb Zählen da der Heap bequem hält auf der Oberseite. Erst wenn alle vom Haufen genommen sind, werden angenommen; erst nachdem so viele wie (und damit wie ) gefunden wurden, akzeptiert mit leerem Heap und Endzustand.$a$$a$$b$$b$$a$$b$$b$$a$$a$$c$$c$$b$$a$$A$

Daher .$\cal{L}(A) = L$

$\mathrm{CFL} \setminus \mathrm{HAL} \neq \emptyset$

Dieser Teil der Antwort bezieht sich nur auf Typ 1.

Betrachten die Menge der geraden Palindrome und nehme an, es ist HA mit .$\mathrm{EPAL} = \{ww^R \mid w \in \{a,b\}\}$$A$$\cal{L}(A) = L$

Vermutung: Wir finden mit undso dass sich nach dem Lesen von bzw. in demselben Zustand befindet und denselben Heap-Inhalt hat . Da sowohl als auch akzeptiert, akzeptiert es daher auch (und ), was ein Widerspruch zu .$w_1, w_2 \in \{a,b\}^*$$w_1 \neq w_2$$|w_1| = |w_2|$$A$$w_1$$w_2$$A$$w_1w_1^R$$w_2w_2^R$$w_1w_2^R \notin \mathrm{EPAL}$$w_2w_1^R$$\cal{L}(A) = \mathrm{EPAL}$

$\mathrm{CSL} \setminus \mathrm{HAL} \neq \emptyset$

Dieser Teil der Antwort bezieht sich sowohl auf Typ 1 als auch auf Typ 2.

Die gleiche Argumentation, die wir für (für Typ 1) verwendet haben, kann verwendet werden, um zu zeigen, dass die kontextsensitive Sprache nicht in ist . { w w | w ∈ { ein , b } * } H A $\mathrm{EPAL}$$\{ww \mid w \in \{a,b\}^*\}$$\mathrm{HAL}$

$\mathrm{HAL} \overset{?}{\subseteq} \mathrm{CSL}$

Dies ist sowohl für Typ 1 als auch für Typ 2 noch offen.

Weitere Factoide

HA scheint orthogonal zu einer Teilmenge der leicht kontextsensitiven Sprachen zu sein, die von Embedded Pushdown Automata akzeptiert werden : Während HA eine begrenzte Anzahl gestapelter Stapel simulieren kann, können sie nicht beliebig viele simulieren (wie es EPA kann). HA kann jedoch auf die oberen Symbole von Stapeln zugreifen, die sich derzeit nicht oben befinden (was EPA nicht kann).