[AAT] EMSO-Formeln: Nur ein Quantor?

[Lukul]

Hallo,
falls jemand zufällig in der AAT drinsteckt: Im Skript von 2003 soll in einer Übung gezeigt werden, dass jede Sprache definierbar ist durch einen EMSO-Satz mit nur einem Mengenquantor. Mich würde interessieren, wie das funktioniert. Wie i.A. von einer Sprache zu einer EMSO-Formel kommt, ist klar, aber wie bringt man das ganze in nur einem Mengenquantor unter? Es gibt da wohl eine Veröffentlichung aus 82, wo Prof. Thomas selbst das bewiesen hat, leider ist diese aber nicht online zugänglich.

[fw]

Wenn du mir deine Mail Adresse gibst, schick ich dir die eingescannte Lösung (ist aber ziemlich abgefahren ).

Kleine weitere Überlegung für dich: Geht es auch ganz ohne Second Order Existenzquantoren, dafür nur mit Allquantoren? (Wenn ich schon so frage, ist die Antwort natürlich ja )
(Habe vor ein paar Tagen ein Prüfungsprotokoll auf s-inf geladen, falls es dir hilft)

[MartinL]

Die Idee dabei ist, dass man den Zustand jeweils in der Menge über mehrere Zeichen binär kodiert. Dafür speichert man jeweils nur jeden x-ten Zustand des Laufes, so dass in der Menge genug Platz ist um die Zustände dort abzulegen. Die Formel muss dann jeweils den Übergang über eine etwas größere Menge von Zuständen kodieren. Das sind aber nur jeweils endlich viele - so dass man das (zwar mit riesigem Friemelaufwand, aber grundsätzlich) machen kann.

[MaoDelinSc]

Ich habe AAT zwar schon im ersten Versuch bestanden und selbst auf die Gefahr hin, dass ich mich jetzt lächerlich mache, aber was ist EMSO?

[palle]

Mal ein Schuss ins Blaue: MSO ist Monadische Second-Order-Logik, E wird für Extended oder Existenziell stehen?

[fw]

letzteres