Testez deux arbres d'expression LTL pour l'équivalence

Question

Y a-t-il un algorithme sur la façon de vérifier si deux expressions LTL (représentées sous forme d'arbres binaires) sont sémantiquement équivalentes?Puisqu'il y a beaucoup de petites équivalences telles que $ a \ droite b \ equiv \ nge a \ vee b $ ou $ f (a) \ équivécuteur true u a $ ainsi que la commutativité, la distribution, etc. qui doivent être pris en compte.
Mon idée initiale était de créer la table de vérité pour les expressions et de les comparer.Mais ensuite, les opérateurs temporels ne seraient pas pris en compte.Créer et comparer l'automate pour chaque expression semble être plutôt inefficace.

Y a-t-il un meilleur moyen de le faire?

Answer 1

Malheureusement, l'approche de la construction d'automates pour chaque formule et de tester leur équivalence est à peu près le mieux que vous puissiez faire.

Le problème de la vérification si une formule LTL est valide, c'est-à-dire qu'elle est satisfaite dans chaque calcul, est une complète PSPACE (il s'agit d'un exercice facile, étant donné que la satisfaction de LTL est complète de PSPACE).

Ainsi, vérifiant si deux formules LTL sont équivalentes est également dure au moins PSPACE dur, car vous pouvez réduire le premier en test d'équivalence avec la formule "vraie".

Pour afficher l'adhésion à PSPACE, vous pouvez adopter l'approche standard de la vérification de l'équivalence de l'automate correspondante "à la volée", sans les construire explicitement.