Testare due alberi di espressione LTL per l'equivalenza

Question

C'è un algoritmo su come controllare se due espressioni LTL (rappresentate da alberi binari) sono semanticamente equivalenti?Dal momento che ci sono molte equivendi più piccoli come $ A \ RightArrow B \ Equiv \ Neg A \ Vee B $ o $ f (A) \ Equiv TRUE U A $ così come commutatività, distribuzione, ecc. Questo deve essere considerato.
La mia idea iniziale è stata quella di creare la tabella di verità per entrambe le espressioni e confrontarle.Ma poi gli operatori temporali non sarebbero presi in considerazione.Creare e confrontare l'automa per ogni espressione suoni come se fosse piuttosto inefficiente.

C'è un modo migliore per farlo?

Answer 1

Sfortunatamente, l'approccio di costruire automati per ogni formula e testare la loro equivalenza è praticamente il meglio che puoi fare.

Il problema di verificare se una formula LTL è valida, cioè, sia che sia soddisfatta in ogni calcolo, è la PSpace Completa (questo è un esercizio facile, dato che LTL SODDEABILY è PSPACE COMPLETO).

Pertanto, controllando se due formule LTL sono equivalenti è anche almeno la pspace difficile, dal momento che è possibile ridurre dal primo test testing equivalenza con la formula "Vero".

Per mostrare l'appartenenza a PSPACE, è possibile adottare l'approccio standard di verificare l'equivalenza delle corrispondenti automati "al volo", senza effettivamente costruendoli esplicitamente.