Witness for the $ UE (\ phi_1, \ phi_2) $ utilizzando BDDS

Question

Volevo chiedere se si conosce un algoritmo per trovare il testimone a $ UE (\ phi_1, \ phi_2) $ (CTL formula "esistere fino") usando BDDS ( Binary decisione Diagramma ). In pratica si dovrebbe usare il punto fisso per il calcolo $ UE (\ phi_1, \ phi_2) $, che è:

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

svolgendo il ricorsione, otteniamo:

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

e così via.

Per generare un testimone (percorso) possiamo fare un controllo di raggiungibilità in avanti all'interno della sequenza di $ Q_i di $, cioè trovare un percorso

$ \ qquad \ displaystyle \ pi = S_1 \ rightarrow s_2 \ rightarrow \ cdots \ rightarrow S_n $

tale che $ s_i \ in Q_ {ni} \ tappo R (s_ {i-1}) $ (dove $ R (s_ {i-1}) = \ {s \ metà R (s_ {i-1 }, s) \} $ e $ R (s_ {i-1}, s $) è il passaggio da $ s_ {i-1} $ a $ s $) dove $ s_0 \ in Q_n $ e $ S_n \ a Q_1 = \ phi_2 $.

Come si può fare questo con BDDS?

Answer 1

Ciò che si descrive è model checking simbolico, ed è trattato in questo serie di diapositive , utilizzando ridotti BDDS ordinati.

In poche parole, è ancora fare l'iterazione di punto fisso, la questione principale è come fare la trasformazione $ Q \ mapsto \ phi_2 \ vee (\ phi_1 \ wedge perla squisi) $ su BDDS. Le operazioni elementari necessari sono ridenominazione (per sostituire senza primer da variabili innescati a $ Q $, ottenendo $ Q '$), le operazioni booleane (per formare $ \ phi_2 \ vee (\ phi_1 \ cuneo R \ wedge Q') $) e astrazione (fare eliminazione quantificatore esistenziale sulle variabili innescati). La generazione testimone può quindi essere fatto in modo simile in avanti dagli stati iniziali, richiedendo al passo $ i $ che $ $ s_i è in $ Q_ {n-i} $ come avete fatto in precedenza.