Témoin de l'UE $ (\ phi_1, \ phi_2) $ en utilisant BDD

Question

Je voulais vous demander si vous connaissez un algorithme pour trouver le témoin de $ EU (\ phi_1, \ phi_2) $ (formule CTL "Exist Jusqu'à") en utilisant BDD ( décision Diagramme binaire ). En pratique, vous devez utiliser le point fixe pour le calcul de $ EU (\ phi_1, \ phi_2) $, ce qui est:

$ \ qquad \ displaystyle UE (\ phi_1, \ phi_2) = \ mu.Q (\ phi_2 \ Vee (\ phi_1 \ wedge EX Q)) $

déroulage la récursion, nous obtenons:

$ \ qquad \ displaystyle \ begin {align}   Q_0 & = \ {textrm false} \\   Q_1 & = \ phi_2 \\   Q_2 & = \ phi_2 \ Vee (\ phi_1 \ wedge EX \ phi_2) \\   \ \ Vdots \ End {align} $

et ainsi de suite.

Pour générer un témoin (chemin), nous pouvons faire une vérification de joignabilité en avant dans la séquence qui est de trouver $, $ Q_i un chemin

$ \ qquad \ displaystyle \ pi = s_1 \ rightarrow s_2 \ rightarrow \ cdots \ rightarrow s_n $

tel que $ S_I \ in Q_ {ni} \ cap R (s_ {i-1}) $ (où $ R (s_ {i-1}) = \ {s \ mid R (s_ {i-1 }, s) \} $ et $ R (s_ {i-1}, s $) est la transition de $ s_ {i-1} $ à $ s $) où $ s_0 \ in Q_n $ et s_n $ \ in Q_1 = \ phi_2 $.

Comment vous pouvez le faire avec BDD?

Answer 1

Ce que vous décrivez est la vérification du modèle symbolique, et il est traité dans cette ensemble de diapositives , en utilisant une réduction BDD commandés.

En un mot, vous faites encore l'itération de point fixe, la principale question étant de savoir comment faire la transformation $ Q \ mapsto \ phi_2 \ Vee (\ phi_1 \ wedge EXQ) $ sur BDD. Les opérations élémentaires dont vous avez besoin sont renommer (pour remplacer désamorcée par des variables amorcées dans $ Q $, obtenir Q '$), des opérations booléennes (pour former $ \ phi_2 \ Vee (\ phi_1 \ wedge R \ wedge Q') $) et abstraction (pour faire élimination des quantificateurs existentielle sur les variables amorcées). La génération des témoins peut être fait de la même avant des états initiaux, exige à l'étape $ i $ que $ S_I $ est en $ Q_ {n-i} $ que vous avez fait ci-dessus.