$2.$ Compositions. Consider the Kripke structure defined in problem $1,$ and let us call it $K_1=(S,S_0,R_1,L_1).$ Next, consider that we had a second copy of that Kripke structure and lets call it $K_2=(T,T_0,R_2,L_2)$ where T contains states $t_0,t_1,$dots,$t_{10},$ and $L_2$ contains a similar labeling function with predicates $q_0,q_1,$ dots,$q_{10}.$

Answer the following questions:

a$.$ How many transitions exist in $K_1?$

b$.$ Given a synchronous composition of $K_1$ and $K_2,$ how many states are there? $($Note: You do not need to analyze whether the states in the composition are reachable.$)$

c$.$ Given an asynchronous composition of $K_1$ and $K_2,$ how many states are there? $($Note: You do not need to analyze whether the states in the composition are reachable.$)$

d$.$ Given a synchronous composition of $K_1$ and $K_2,$ how many predicates are there? $($Note: Use as few predicates as possible.$)$

e$.$ Given an asynchronous composition of $K_1$ and $K_2,$ how many predicates are there?

f$.$ Given a synchronous composition of $K_1$ and $K_2,$ give an upper bound estimate on the number of transitions?

g$.$ Given an asynchronous composition of $K_1$ and $K_2,$ give an upper bound estimate on the number of transitions?

$3.$ BDD Terminal Cases and Operation BDD$\_$OR$.$

a$.$ Specify a set of terminal cases for BDD$\_$AND$($f$,$g$).$

b$.$ Justify that the operation BDD$\_$OR can be derived from BDD$\_$AND by replacing the terminal cases. Specify a set of terminal cases for BDD$\_$OR$($f$,$g$).$

$4.$ BDDs$.$

a$.$ Write a BDD for $f=w+x^{\text{'}}+y+z.$ Use the ordering $g=w^{**}{x}^{**}zh=w^{**}x**z^{\text{'}}w.$

$d.$ Represent all three $BDDsas$ one shared $BDD$ structure.

$e.$ Construct a $BDD$ for $BD{D}_{A}ND(f,g).$ Use the $BD{D}_{A}ND$ algorithm presented $in$ class.

$f.$ Construct a $BDD$ for $BD{D}_{O}R(g,h).$ Use a 'modified' $BD{D}_{A}ND$ algorithm $(see$ problem $3.b.)w.$

$c.$ Write a $BDD$ for $h=w^{**}x**z^{\text{'}}.$ Use the ordering $w.$

$d.$ Represent all three $BDDsas$ one shared $BDD$ structure.

$e.$ Construct a $BDD$ for $BD{D}_{A}ND(f,g).$ Use the $BD{D}_{A}ND$ algorithm presented $in$ class.

$f.$ Construct a $BDD$ for $BD{D}_{O}R(g,h).$ Use a 'modified' $BD{D}_{A}ND$ algorithm $(see$ problem $3.b.)w.$

$b.$ Write a $BDD$ for $g=w^{**}{x}^{**}z.$ Use the ordering $w.$

$c.$ Write a $BDD$ for $h=w^{**}x**z^{\text{'}}.$ Use the ordering $w.$

$d.$ Represent all three $BDDsas$ one shared $BDD$ structure.

$e.$ Construct a $BDD$ for $BD{D}_{A}ND(f,g).$ Use the $BD{D}_{A}ND$ algorithm presented $in$ class.

$f.$ Construct a $BDD$ for $BD{D}_{O}R(g,h).$ Use a 'modified' $BD{D}_{A}ND$ algorithm $(see$ problem $3.b.)$

Reading Assignment

Please review the slides to solve the following problems.

In addition, there are three documents on BDDs available on Courseworks that you should read in case you are interested in more details.

a$.$ Brace article on "Efficient Implementation of a BDD package".

b$.$ Meinel book $($Chapters $6-9).$

c$.$ Meinel book $($Chapters $10-11).$

BDDs are also covered by a few books in the class library $($see slides$).$

$1.$ Problems

Explicit state model checking. Consider a system, where we have states $s_0,s_1,s_2,$dots,$s_9,s_{10}.$ The initial state is $s_0$ only. There is a transition from a state $s_i$ to $s_{i+5},$ for all $0i5.$ Additionally, there are transitions from $s_i$ to $s_{i-3},$ for all $3i10.$ For each state $s_i$ we define an associated atomic predicate $p_i.$ That is$,p_0$ is true in $s_0$ and nowhere else, $p_1$ is true in $s_1$ and nowhere else, dots,$p_{10}$ is true in $s_{10}$ and nowhere else.

Using the explicit$-$state model checking algorithm presented in class, determine if the following properties hold.

a$.EF{p}_1$

b$.AF{p}_2$

c$.AG(p_{9}AF{p}_3)$

d$.AG(p_{4}EF{p}_{10})$

Note: Please submit a drawing of the Kripke Structure as part of your answer. Please note that you are NOT asked to simply answer the questions by looking at the Kripke Structur