Beweisen, dass eine (Baum-) Sprache nicht von Buchi erkennbar ist

7

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.A={a,b}T={tTAωevery path in t contains a finite number of a}T

Jetzt können wir die folgenden Teilmengen von Bäumen wobei an Positionen eins : mit .tnTttnaϵ,1m10,1m101m20,,1m101m201mn0mi>0

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 .A=(Q,A,Δ,q0,F)T|Q|=n+1q0ttnrAt

Behauptung: There exists uv<w such that r(u)=r(w)=sF and t(v)=a.

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.)tvttn+1twtvrrwwvaA

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.tt2ntn

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 wiederverwendenrsF1m101m201mn0ttn+1tnxr(x)=sarrxrsum 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.st2n

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?tn1tn2tn ttn

Bakuriu
quelle

Antworten:

3

Die Idee ist , wie folgt mit den zu spielen .mi

Sie sich einen Baum , der In , und nirgendwo anders. Schauen Sie sich den Pfad - ein akzeptierender Lauf hat unendlich viele akzeptierende Zustände. Warten Sie, bis ein solcher Akzeptanzzustand erreicht wurde, und setzen Sie erst dann auf , wobei groß genug ist.t1aϵ1ωa1m10m1

Schauen Sie sich nun den Pfad , wieder hat er schließlich einen akzeptierenden Zustand, bezeichnen Sie die Länge bis dazu mit , setzen Sie ein bei und schauen Sie bei . Inzwischen haben Sie fast das, was Sie wollten - zwei akzeptierende Zustände mit einem dazwischen (informell gesprochen). Es ist jedoch noch nicht garantiert, dass beide akzeptierenden Zustände gleich sind. Um letzteres durchzusetzen, wiederholen wir den Vorgang mal, wodurch die Anzahl der akzeptierenden Zustände erschöpft ist, und nach dem Pigeonhole-Prinzip müssen zwei akzeptierende Zustände gleich sein.1m101ωm2a1m101m201m101m201ωan

Shaull
quelle
Sie haben nicht einmal die Zahl der Staaten berücksichtigen müssen - nur zur Kenntnis , dass dieser Ansatz Sie gibt (für einen bestimmten Automaten ) eine unendliche Folge , so dass jeder für , eine akzeptierende Zustand erreicht mal auf , und daher wird die Grenze akzeptiert, obwohl unendlich viele s . Am1,m2,kAk1m101m201mk01m101m200
Klaus Draeger
Richtig, aber das OP wollte speziell die Anzahl der durch begrenzen , für die Sie die Anzahl der Zustände benötigen. min+1
Shaull
Dies ist mehr oder weniger das, worüber ich nachgedacht habe, aber es beweist etwas Schwächeres als die Behauptung. Damit beweisen Sie, dass und erfolgreicher Lauf von auf so dass <claim>. Während in dem vom Professor angegebenen Beweis und erfolgreicher Lauf von über ti <claim> gilt. Das Problem ist , dass , wenn Sie fixiert man nicht wirklich spielen mit denen s , wie Sie wollen. Jetzt frage ich mich, ob die Behauptung des Professors tatsächlich wahr ist oder ob dies das Beste ist, was wir erreichen können. ttnrAtttnrAttmi
Bakuriu
1
Für jeden erfolgreichen Lauf ist die Behauptung eindeutig falsch, da der Automat eine Komponente haben kann, die einen Punkt errät, von dem aus nie wieder angetroffen wird. Es ist klar, dass jedes mindestens einen solchen akzeptierenden Lauf haben wird ...attn
Shaull