Testen Sie zwei LTL-Expressionsbäume für Äquivalenz

Question

Gibt es einen Algorithmus, wie man prüft, ob zwei LTL-Ausdrücke (als binäre Bäume dargestellt) semantisch gleichwertig sind?Da gibt es viele kleinere Äquivalenzen wie $ A \ Rightsarrow B \ EQUIV \ NEG A \ Vee B $ oder $ F (A) \ Equiv True U A $ sowie Kommutativität, Vertriebsbildung usw., die berücksichtigt werden müssen.
Meine erste Idee bestand darin, die Wahrheitstabelle für beide Ausdrücke zu erstellen und sie zu vergleichen.Dann würden die zeitlichen Betreiber jedoch nicht berücksichtigt werden.Erstellen und Vergleichen des Automaten für jeden Ausdrucksgeräusche, als wäre es eher ineffizient.

Gibt es einen besseren Weg, dies zu tun?

Answer 1

Leider ist der Ansatz von Automaten für jede Formel und das Testen ihrer Äquivalenz so ziemlich das Beste, was Sie tun können.

Das Problem der Überprüfung, ob eine LTL-Formel gültig ist, dh egal ob er in jeder Berechnung erfüllt ist, ist PSPACE komplett (dies ist eine einfache Übung, da die LTL-Erfüllung PSPACE komplett ist).

Wenn Sie also zwei LTL-Formeln gleichwertig sind, ist daher auch mindestens PSPACE hart, da Sie von Anfang an reduzieren können, indem Sie die Äquivalenz mit der Formel "True" testen.

Um die Mitgliedschaft in PSPACE anzuzeigen, können Sie den Standardansatz der Überprüfung der Gleichwertigkeit der entsprechenden Automaten "auf der Fliege" annehmen, ohne sie eigentlich explizit zu errichten.