Testigo de $ UE (\ phi_1, \ phi_2) $ usando BDDs

Question

Yo quería preguntarle si sabe un algoritmo para encontrar el testigo de $ UE (\ phi_1, \ phi_2) $ (CTL fórmula "existiendo hasta") usando BDDs ( Decisión binario Esquema ). En pratice se debe utilizar el punto fijo para el cálculo de $ UE (\ phi_1, \ phi_2) $, es decir:

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

desenrollar la recursividad, obtenemos:

$ \ qquad \ displaystyle \ begin {align} Q 0 y = \ {textrm false} \\ Q_1 & = \ \\ phi_2 Q_2 & = \ phi_2 \ vee (\ phi_1 \ wedge EX \ phi_2) \\ \ \ Vdots \ End {align} $

y así sucesivamente.

Para generar un testigo (ruta) que podemos hacer una comprobación de accesibilidad hacia delante dentro de la secuencia de $ Q_i de $, es encontrar un camino

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

tal que $ S_I \ en Q_ {Ni} \ cap R (s_ {i-1}) $ (donde $ R (s_ {i-1}) = \ {s \ mediados R (s_ {i-1 }, s) \} $ y $ R (s_ {i-1}, s $) es la transición de $ s_ {i-1} $ a $ s $) donde $ S_0 \ en Q_n $ y $ s_n \ in q_1 = \ phi_2 $.

¿Cómo se puede hacer esto con BDDs?

Answer 1

Lo que usted describe es simbólica la verificación de modelos, y se trata en este conjunto de diapositivas , utilizando BDDs ordenados reducidos.

En pocas palabras, que todavía lo hacen la iteración punto fijo, la cuestión principal es cómo hacer la transformación $ Q \ mapsto \ phi_2 \ vee (\ phi_1 \ wedge EXQ) $ en BDDs. Las operaciones elementales que necesita son el cambio de nombre (para reemplazar sin imprimación por variables con prima en $ Q $, obteniendo $ Q '$), operaciones booleanas (que forman $ \ phi_2 \ vee (\ phi_1 \ wedge R \ wedge Q') $) y abstracción (que hacer eliminación de cuantificadores existencial de las variables con prima). La generación de testigos a continuación se puede hacer de manera similar hacia delante desde los estados iniciales, lo que requiere en el paso i $ $ $ $ que está en S_I $ Q_ {n-i} $ tal como lo hizo anteriormente.