Roberto Sebastiani
DISI, Universit` a di Trento, Italy June 17
th, 2021
769857918 Name (please print):
Surname (please print):
Given the following OBDD, with the ordering { A5, A1, A3, A2, A4},
A5
A3
A2
A4
A1
⊤ ⊥
⊤
⊤
⊤
⊤
⊤
⊥
⊥
⊥
⊥
⊥
for each of the following Boolean formulas, say whether the OBDD represents it or not.
(a) (¬A5 → (¬A1 → (¬A3 → (¬A2 → A4)))) (b) ( A2∨ A1∨ A5∨ A3∨ A4)
(c) ( A3∧ A5∧ A4∧ A1∧ A2)
(d) ( A5 → ( A1 → ( A3 → ( A2 → ¬A4))))
[SCORING [0...100]:
• +25pts for each correct answer
• -25pts for each incorrect answer
• 0pts for each unanswered question
Consider the following Kripke Model M :
p, ¬q s
3¬p, q s
0p, q s
1For each of the following facts, say if it is true or false in LTL.
(a) M |= GFp (b) M |= FG¬p (c) M |= pUq
(d) M |= (GF¬p ∧ GF¬q) → p
[SCORING [0...100]:
• +25pts for each correct answer
• -25pts for each incorrect answer
• 0pts for each unanswered question ]
Consider the following fair Kripke Model M :
F1 F2
p, ¬q s
3¬p, q s
0p, q s
1For each of the following facts, say if it is true or false in LTL.
(a) M |= GFp (b) M |= FG¬p (c) M |= pUq
(d) M |= (GF¬p ∧ GF¬q) → p
[SCORING [0...100]:
• +25pts for each correct answer
• -25pts for each incorrect answer
• 0pts for each unanswered question ]
For each of the following fact regarding Buchi automata, say if it true or false.
(a) The following BA represents FGq:
q q
q
(b) The following BA represents FGq:
q q
q
(c) The following BA represents pUq:
p
p q
q
(d) The following BA represents pUq:
p
p q
q
[SCORING [0...100]:
• +25pts for each correct answer
• -25pts for each incorrect answer
• 0pts for each unanswered question ]
Consider the following pair of ground and abstract machines M and M′: M :
MODULE main VAR
v1 : boolean;
v2 : boolean;
v3 : boolean;
ASSIGN
init(v1) := FALSE;
init(v2) := TRUE;
init(v3) := FALSE;
TRANS
(next(v1) <-> v2) &
(next(v2) <-> v3) &
(next(v3) <-> v1)
M′:
MODULE main VAR
v1 : boolean;
v2 : boolean;
v3 : boolean;
ASSIGN
init(v1) := FALSE;
init(v2) := TRUE;
TRANS
(next(v1) <-> v2) &
(next(v2) <-> v3)
For each of the following facts, say which is true and which is false.
(a) M′ simulates M . (b) M simulates M′.
(c) For every Boolean property φ on v1,v2, if M′ |= Gφ, then M |= Gφ, (d) For every Boolean property φ on v1,v2, if M |= Gφ, then M′ |= Gφ,
[SCORING [0...100]:
• +25pts for each correct answer
• -25pts for each incorrect answer
• 0pts for each unanswered question ]
Consider the following piece of a much bigger formula, which has been fed to a CDCL SAT solver:
c1 :¬A9∨ A12∨ ¬A1
c2 : A9∨ ¬A7∨ ¬A3
c3 :¬A11∨ A5∨ A2
c4 :¬A10∨ ¬A12∨ A11
c5 :¬A11∨ A6∨ A4
c6 :¬A9∨ A10∨ ¬A1
c7 : A9∨ A8∨ ¬A3
c8 :¬A5∨ ¬A6
c9 : A7∨ ¬A8∨ A13
...
Suppose the solver has decided, in order, the following literals (possibly interleaved by others not occurring in the above clauses):
{..., A1, ...¬A2, ...¬A4, ... A3, ...¬A13, ..., A9}
(a) List the sequence of unit-propagations following after the last decision, each literal tagged (in square brackets) by its antecedent clause
(b) Derive the conflict clause via conflict analysis by means of the 1st-UIP technique
(c) Using the 1st-UIP backjumping strategy, update the list of literals above after the backjumping step and the unit-propagation of the UIP
[SCORING: [0...100], 25 points each for correct answers to (a) and (c), 50 points for correct answer to (b). No penalties for wrong answers..]
7
Given the following generalized B¨uchi automaton Adef=⟨Q, Σ, δ, I, F T ⟩, {a, b} being labels, with two sets of accepting states F T def={F 1, F 2} s.t. F 1def={s2}, F 2def={s1}:
s1 s2
F2 F1
a a
b b
convert it into an equivalent plain B¨uchi automaton.
[SCORING: [0...100], 100 pts for a correct answer. No penalties for a wrong answer.]
Consider the following LTL formula:
φ def= (Fr)→ (pUq)
and the following three states of the construction of the tableau Tφ of φ:
S1 : ⟨ q, p, ¬X(pUq), r, XFr⟩
S2 : ⟨¬q, p, X(pUq), r, ¬XFr⟩
S3 : ⟨ q, ¬p, ¬X(pUq), ¬r, ¬XFr⟩
For each of the following statements, say if it is true or false.
(a) S2 is a successor of S1 in Tφ. (b) S3 is a successor of S2 in Tφ. (c) S3 is an initial state of Tφ. (d) S2 is an accepting state of Tφ.
[SCORING [0...100]:
• +25pts for each correct answer
• -25pts for each incorrect answer
• 0pts for each unanswered question ]
[SCORING: [0...100], 25 pts for each correct answer. No penalties for wrong answers.]
9
Given the following LTL Model Checking problem M |= φ expressed in NuXMV input language:
MODULE main
VAR x : boolean; y : boolean;
INIT (!x & !y)
TRANS (next(x) <-> !x) & (next(y) <-> (x<->y)) LTLSPEC G (x<->y)
1. Write a Boolean formula corresponding to the Bounded Model Checking problem with k = 2.
2. Is there a solution? If yes, find the corresponding execution.
3. From the answers of questions 1) and 2) we can deduce (a) that M |= φ.
(b) that M ̸|= φ.
(c) nothing.
[SCORING: [0...100], 50 pts for question 1, 25pts each for questions 2, 3. No penalties for wrong answers..]
Consider the following switch e in a timed automaton:
L
1(y ≤ 5) (y ≥ 4) a y := 0 L
2and consider the zone Z1def=⟨L1, φ⟩ s.t
φdef= (x≥ 0) ∧ (x ≤ 2) ∧ (y ≥ 1) ∧ (y ≤ 3) ∧ (y − x ≤ 2).
Compute succ(φ, e), displaying the process in a cartesian graph.
[SCORING: [0...100], 100 pts for a correct answer, -33 pts for a wrong answer, 0pts if unanswered..]
