$ eu（ phi_1、 phi_2）の証人$ bdds

Question

$ eu（ phi_1、 phi_2）$（ctl式は「存在する」）の証人を見つけるためにアルゴリズムを知っているかどうかを尋ねたかった（bdds（ctl式 "）バイナリ決定図）。プラチスでは、$ EU（ phi_1、 phi_2）$を計算するために固定点を使用する必要があります。

$ qquad displaystyle eu（ phi_1、 phi_2）= mu.q（ phi_2 vee（ phi_1 wedge ex q））$

再帰を巻き戻すと、

$ qquad displaystyle begin {align} q_0＆= textrm {false} q_1＆= phi_2 q_2＆= phi_2 vee（ phi_1 wadge ex phi_2） vdots end end eind {align} $

等々。

証人（パス）を生成するために、$ q_iの$のシーケンス内でフォワードリーチビリティチェックを行うことができます。

$ qquad displaystyle pi = s_1 rightArrow s_2 rightArrow cdots rightArrow s_n $

$ s_i in q_ {ni} cap r（s_ {i-1}）$（ここで$ r（s_ {i-1}）= {s mid r（s_ {i-1}、s ）} $ and $ r（s_ {i-1}、s $）は、$ s_ {i-1} $から$ s $への遷移です。 phi_2 $。

BDDSでこれを行うにはどうすればよいですか？

Answer 1

あなたが説明するのはシンボリックモデルチェックであり、それはこれで扱われます スライドのセット, 、縮小された順序付きBDDを使用します。

一言で言えば、あなたはまだ修正ポイントの反復を行います。主な問題は、bddsで変換$ q map phi_2 vee（ phi_1 ded exq）$を行う方法です。必要な基本操作は、名前を変更します（$ q $のプライミング変数に合わせて$ q '$を取得）、ブール操作（$ phi_2 vee（ phi_1 wedge r dedge q'）$を形成するため）および抽象化（プライミングされた変数で実存的な量子除去を行うため）。目撃者の世代は、最初の状態から同様に前方に行うことができ、ステップ$ i $で$ s_i $が上記のように$ q_ {ni} $であることを要求します。