Свидетель для $ eu ( phi_1, phi_2) $ с использованием BDDS

Question

Я хотел спросить, знаете ли вы алгоритм, чтобы найти свидетеля для $ eu ( phi_1, phi_2) $ (формула CTL «существует до»), используя BDD (Бинарная диаграмма решений) В Pratice вы должны использовать фиксированную точку для расчета $ 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 wedge ex phi_2) vdots end {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 ) } $ и $ r (s_ {i-1}, s $)-это переход от $ s_ {i-1} $ to $ s $), где $ s_0 in q_n $ и $ s_n in q_1 = phi_2 $.

Как можно сделать это с BDD?

Answer 1

То, что вы описываете, - это символическая проверка модели, и она рассматривается в этом набор слайдов, используя уменьшенные упорядоченные BDD.

Короче говоря, вы все еще делаете итерацию Fix -Point, основная проблема заключается в том, как сделать преобразование $ q mapsto phi_2 vee ( phi_1 wedge exq) $ на BDDS. Элементарные операции, которые вам нужны, - это переименование (для замены безвимированных замыкаемыми переменными в $ Q $, получая $ Q '$), логические операции (для формирования $ phi_2 vee ( phi_1 wedge r wedge q') $) и и Абстракция (чтобы сделать экзистенциальный элиминация квантификаторов на первичных переменных). Поколение свидетелей может быть сделано аналогичным образом вперед от начальных состояний, требуя, чтобы на шаге $ i $ $ s_i $ находится в $ Q_ {ni} $, как вы это делали выше.