Was ist am einfachsten von allen anständigen LTL-zu-Buchi-Übersetzungen oder anderen LTL-Verifizierungsalgorithmen zu implementieren?

Ich schreibe einen Spielzeugmodellprüfer und bin an dem Punkt angelangt , an dem es Zeit ist, die Übersetzung von LTL in Buchi-Automaten zu implementieren.

Aus verschiedenen offensichtlichen Gründen möchte ich, dass der Algorithmus einfach ist :) zB möchte ich, dass der Code so lange wie möglich extrem klar und präzise bleibt.

Ich habe mir den Ansatz "Lokale Automaten + Eventualitätsautomaten" angesehen, der in mehreren Tutorials beschrieben wurde, aber er scheint weder einfach zu implementieren / zu verstehen (der Korrektheitsnachweis ist ziemlich groß), noch liefert er kleine Automaten. Also implementiere ich es nicht, bis ich sicher bin, dass ich es nicht bereuen werde :)

Daher wäre ich dankbar für Verweise auf Artikel, die einfache und effiziente Algorithmen für diese Übersetzung beschreiben, oder vielleicht einfache und ineffiziente - dann wären auch Artikel zur Minimierung von Buchi-Automaten willkommen :)

... oder gibt es vielleicht interessante alternative Ansätze zur LTL-Verifikation?

Als Referenz finden Sie hier eine Genealogie der LTL-zu-Buchi-Übersetzungsalgorithmen http://spot.lip6.fr/wiki/LtlTranslationAlgorithms . Kann jemand etwas dazu sagen?

Eine Konstruktion, die nicht auf der SPOT- Website aufgeführt ist, wurde in einer Umfrage von Demri & Gastin, Spezifikation und Verifizierung unter Verwendung von Temporal Logics , 2009, angegeben. Die Konstruktion ist einfach und liefert relativ kleine Automaten, so dass sie für kleine Formeln von Hand ausgeführt werden kann ist gut für das Unterrichten (wie ich es benutze), kann aber auch hilfreich sein, um eine Implementierung zu debuggen. Ich würde nicht darauf wetten, dass es effizienter ist als das von SPOT verwendete.

In Bezug auf die Minimierung gibt es keinen kanonischen Minimal-Büchi-Automaten für eine bestimmte reguläre Sprache. Um kleinere Automaten zu erhalten, kann man den Automaten durch eine Simulationsbeziehung quotieren. Ein klassischer Artikel zu diesem Thema stammt von Etessami, Wilke & Schuller, Fair Simulation Relations, Parity Games und State Space Reduction für Büchi Automata , SIAM Journal on Computing 34: 1159–1175, 2005.$\omega$

Ich würde die Übersetzung betrachten, die durch alternierende Automaten geht. (Siehe Vardis Artikel "Alternierende Automaten und Programmüberprüfung"). Es ist eine sehr elegante Übersetzung von LTL zu alternierenden Automaten, und dann können Sie Mihano Ayashi (das auch elegant ist - es ist eine doppelte Teilmengenkonstruktion) verwenden, um zu nicht deterministischen Buchi-Automaten zu gelangen.