Sind nicht deterministische Baumlaufautomaten stärker als deterministische?

9

Update: Es scheint, dass dieses Problem kürzlich untersucht und gelöst wurde. Siehe diesen Wiki-Artikel: http://en.wikipedia.org/wiki/Tree_walking_automaton Und auch diese Umfrage: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf

Angenommen, anstelle der üblichen Wortgruppe {0,1} * sind unsere Wörter nicht linear, sondern werden in einer Baumstruktur angegeben. Um zu verhindern, dass unsere Maschinen "verloren gehen", definieren Sie unsere Wörter als die Menge der binären, eingebetteten Arboreszenzen. (Jedes Wort ist also ein Baum, bei dem jede Kante von einer bestimmten Wurzel mit Grad zwei weg gerichtet ist, jeder andere Nicht-Blatt-Scheitelpunkt Grad drei hat und jede Kante links oder rechts so gekennzeichnet ist, dass zwei beliebige Kanten von der beginnen Der gleiche Scheitelpunkt hat unterschiedliche Bezeichnungen.) Eine Sprache ist eine Menge solcher Bäume. (Beachten Sie, dass keine Nullen und Einsen auf die Eckpunkte geschrieben werden müssen, da diese ohnehin durch lokales Ändern der Bäume simuliert werden können.) Wenn eine Maschine "einen Baum liest", beginnt sie an der Wurzel und kann erkennen, ob eine gegeben ist Scheitelpunkt ist die Wurzel,

Stimmt es in diesem Modell, dass jede Sprache, die von einem nicht deterministischen endlichen Zustandsautomaten erkannt werden kann, auch von einem deterministischen endlichen Zustandsautomaten erkannt werden kann?

Beachten Sie, dass dies der Fall ist, wenn das Band das übliche lineare Band ist, da jeder 2-NFA mit einem 2-DFA (auch mit einem DFA) simuliert werden kann. Ich fragte bereits eine spezielle Instanz des Problems hier , die durch gelöst wurde Kristoffer . Die Motivation wäre zu lösen diese .

cc.complexity-theory automata-theory space-bounded dfa domotorp
quelle
2
Ich würde vorschlagen , den Titel zu modifizieren „nicht-deterministisch zu schweigen von Bäumen zu Fuß Automaten“.
Sylvain

Antworten:

6

Für Baumautomaten haben Sie folgende Ergebnisse:

  • Deterministische Bottom-Up-Baumautomaten haben dieselbe Ausdruckskraft wie nicht deterministische Bottom-Up-Baumautomaten.

  • Deterministische Top-Down-Baumautomaten sind schwächer als nicht deterministische Top-Down-Baumautomaten.

Weitere Details finden Sie im Tree Automata- Buch.

Es scheint, dass Sie an Top-Down-Baumautomaten interessiert sind, daher lautet die Antwort auf Ihre Frage Nein . Sie müssen natürlich prüfen, ob Top-Down-Baumautomaten tatsächlich das sind, woran Sie interessiert sind.

Dave Clarke
quelle
Nein, keine davon, aber der Wiki-Artikel hatte einen Link zu dem Begriff, den ich definiert habe: en.wikipedia.org/wiki/Tree_walking_automaton
domotorp