Ich überprüfe einige Notizen zu Baumautomaten und versuche, einen Beweis dafür zu finden, dass der Professor unvollständig ist. Die Aussage lautet:
Sei und . Beweisen Sie, dass Buchi nicht erkennbar ist.
Jetzt können wir die folgenden Teilmengen von Bäumen wobei an Positionen eins : mit .
Nehmen wir nun an, dass der Buchi-Automat ist, der mit erkennt und erscheinen nur an der Wurzel seiner Berechnungen. Sei und ein erfolgreicher Lauf von auf .
Behauptung:
Wenn wir zeigen, dass die Behauptung wahr ist, können wir die ursprüngliche Aussage beweisen: Nehmen Sie den Teilbaum und erhalten Sie ein indem Sie den Teilbaum durch . Wir haben, dass es einen Lauf gibt, der bis zur Position für mit identisch ist und bei der gleichen Folge von Zuständen folgt wie bei und daher akzeptiert. Wiederholen Sie den Vorgang und Sie erhalten einen Zweig mit unendlichem s, der von akzeptiert wird . (Dies ist nur die grobe Idee, es erfordert ein wenig Formalismus, aber es ist nicht der Punkt der Frage.)
Meine Frage ist: Wie beweise ich den Anspruch?
Ich kann zeigen, dass es ein mit dieser Eigenschaft gibt (was für den Rest des Beweises tatsächlich gut genug ist), aber nicht, dass bei einem festen die Anweisung für einen erfolgreichen Lauf gilt.
Meine Idee ist einfach: Wenn akzeptiert, muss ein unendlich oft in einem Pfad existieren, der durch . Nehmen Sie dann einen Baum , der mit identisch ist, bis zu der Position an der auf diesem Pfad ist, und fügen Sie ein unterhalb dieser Position hinzu. Jetzt wird dieser Baum noch vom Automaten akzeptiert und es gibt einen akzeptierenden Lauf mit bis zur Position identisch ist , aber dann kann nicht wiederverwendenum denselben Pfad zu akzeptieren (ansonsten haben wir die drei Zustände des Anspruchs gefunden) und muss daher einen anderen Zustand . Wiederholen Sie dies für alle Endzustände und Sie haben, dass mit dieser Eigenschaft ausgeführt werden muss.
Gibt es eine Möglichkeit, diese Art von Argumentation auf , usw. anzuwenden , um das Ergebnis für ? Es sieht höchstens so aus, als könnte ich beweisen, dass es ein mit einem Lauf mit dieser Eigenschaft gibt, während der Anspruch stärker ist. Oder gehe ich in die falsche Richtung?
quelle