Modello basato su Automatoni che controlla le tracce finite

Question

Voglio verificare se una formula in Finite LTL è valida su una traccia lineare finita.

Per le tracce in Info creerei una struttura di Kripke della traccia e un automa di Büchi per la formula negata e controlla se l'intersezione è vuota. Questo funzionerebbe anche con una traccia finita e una formula in FLTL?Ho già provato ad aggiungere un'altra proposta atomica "vivo" alla struttura di Kripke e Automaton (come qui https://spot.lrdhe.epita.fr/tut12.html ).Ma come potrei farlo senza questa proposta atomica aggiuntiva?

Answer 1

La cosa bella delle tracce finite è che finiscono ad un certo punto.LTLF è ora una logica in cui puoi guardare solo nel futuro, e non in passato.

Ciò significa che etichetta ogni personaggio nella parola tramite le quali le sottomaruli della tua formula LTLF tengono per una parola a partire da quel personaggio.Inizi con l'ultimo carattere e applichi la semantica di ltlf lì.Quindi fai lo stesso per il secondo carattere, dove puoi usare il fatto che per l'ultimo carattere, sai già quali sottomarule LTL Hold.

E poi continui in questo modo fino a quando non colpisci la prima lettera.Una volta che hai finito, sai per tutte le sottomarule se si tengono lì.Devi solo guardare l'intera formula come sottofigurazione e hai finito.