Automatische Modellprüfung bei endlichen Spuren

Question

Ich möchte prüfen, ob eine Formel in Finite LTL auf einer endlichen, linearen Spur gültig ist.

Für Inspit-Spuren würde ich eine Kripke-Struktur der Spur und einen Büchi-Automaton für die negierte Formel erstellen und prüfen, ob die Kreuzung leer ist. Würde dies auch mit einer endlichen Spur und Formel in FLTL arbeiten?Ich habe bereits versucht, den Kripke-Struktur und Automaton einen weiteren atomaren Satz "lebend" hinzuzufügen (wie hier https://spot.lrde.epita.fr/tut12.html ).Aber wie könnte ich es ohne diesen zusätzlichen atomaren Satz tun?

Answer 1

Das Schöne an endlichen Spuren ist, dass sie irgendwann enden.LTLF ist jetzt eine Logik, in der Sie nur in die Zukunft suchen können, und nicht in der Vergangenheit.

Dies bedeutet, dass Sie jedes Zeichen in dem Wort beschriften, mit dem Unterformulas Ihrer LTLF-Formel für ein Wort, das von diesem Zeichen beginnen, ein Wort aufnehmen.Sie beginnen mit dem letzten Zeichen und wenden einfach die Semantik von LTLF dort an.Dann machst du dasselbe für das zweitletzte Zeichen, wo du die Tatsache nutzen kannst, dass du für den letzten Charakter bereits weiß, welche LTL-Unterformulaturen halten.

Und dann fahren Sie auf diese Weise fort, bis Sie den ersten Buchstaben treffen.Sobald Sie damit fertig sind, wissen Sie für alle Unterformulaturen, wenn sie dort halten.Sie müssen sich nur auf die gesamte Formel als Unterformel ansehen und fertig sind.