Introduction to Formal Methods Chapter 05: Symbolic CTL Model Checking

(1)

Introduction to Formal Methods

Chapter 05: Symbolic CTL Model Checking

Roberto Sebastiani

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it URL: http://disi.unitn.it/rseba/DIDATTICA/fm2020/

Teaching assistant:Enrico Magnago– enrico.magnago@unitn.it

CDLM in Informatica, academic year 2019-2020

last update: Monday 18^thMay, 2020, 14:48

Copyright notice: some material (text, figures) displayed in these slides is courtesy of R. Alur, M. Benerecetti, A. Cimatti, M.

Di Natale, P. Pandya, M. Pistore, M. Roveri, and S.Tonetta, who detain its copyright. Some exampes displayed in these slides are taken from [Clarke, Grunberg & Peled, “Model Checking”, MIT Press], and their copyright is detained by the authors. All the other material is copyrighted by Roberto Sebastiani. Every commercial use of this material is strictly forbidden by the copyright laws without the authorization of the authors. No copy of these slides can be displayed in public

without containing this copyright notice.

(2)

Outline

1

Motivations

2

Ordered Binary Decision Diagrams

3

Symbolic representation of systems

4

Symbolic CTL Model Checking

5

A simple example

6

Symbolic CTL M.C: efficiency issues

7

Exercises

(3)

Outline

1

Motivations

2

Ordered Binary Decision Diagrams

3

Symbolic representation of systems

4

Symbolic CTL Model Checking

5

A simple example

6

Symbolic CTL M.C: efficiency issues

7

Exercises

(4)

The Main Problem of CTL M.C. State Space Explosion

The bottleneck:

Exhaustive analysis may require to store all the states of the Kripke structure, and to explore them one-by-one

The state space may be exponential in the number of components and variables

(E.g., 300 Boolean vars =⇒ up to 2

³⁰⁰

≈ 10

¹⁰⁰

states!) State Space Explosion:

too much memory required

too much CPU time required to explore each state

A solution: Symbolic Model Checking

(5)

The Main Problem of CTL M.C. State Space Explosion

The bottleneck:

Exhaustive analysis may require to store all the states of the Kripke structure, and to explore them one-by-one

The state space may be exponential in the number of components and variables

(E.g., 300 Boolean vars =⇒ up to 2

³⁰⁰

≈ 10

¹⁰⁰

states!) State Space Explosion:

too much memory required

too much CPU time required to explore each state

A solution: Symbolic Model Checking

(6)

Symbolic Model Checking

Symbolic representation:

manipulation of sets of states (rather than single states);

sets of states represented by formulae in propositional logic;

set cardinality not directly correlated to size

expansion of sets of transitions (rather than single transitions);

(7)

Symbolic Model Checking

Symbolic representation:

manipulation of sets of states (rather than single states);

sets of states represented by formulae in propositional logic;

set cardinality not directly correlated to size

expansion of sets of transitions (rather than single transitions);

(8)

Symbolic Model Checking

Symbolic representation:

manipulation of sets of states (rather than single states);

sets of states represented by formulae in propositional logic;

set cardinality not directly correlated to size

expansion of sets of transitions (rather than single transitions);

(9)

Symbolic Model Checking

Symbolic representation:

manipulation of sets of states (rather than single states);

sets of states represented by formulae in propositional logic;

set cardinality not directly correlated to size

expansion of sets of transitions (rather than single transitions);

(10)

Symbolic Model Checking [cont.]

two main symbolic techniques:

Binary Decision Diagrams (BDDs)

Propositional Satisfiability Checkers (SAT solvers) Different model checking algorithms:

Fix-point Model Checking (historically, for CTL)

Fix-point Model Checking for LTL (conversion to fair CTL MC) Bounded Model Checking (historically, for LTL)

Invariant Checking

...

(11)

Symbolic Model Checking [cont.]

two main symbolic techniques:

Binary Decision Diagrams (BDDs)

Propositional Satisfiability Checkers (SAT solvers) Different model checking algorithms:

Fix-point Model Checking (historically, for CTL)

Fix-point Model Checking for LTL (conversion to fair CTL MC) Bounded Model Checking (historically, for LTL)

Invariant Checking

...

(12)

Outline

1

Motivations

2

Ordered Binary Decision Diagrams

3

Symbolic representation of systems

4

Symbolic CTL Model Checking

5

A simple example

6

Symbolic CTL M.C: efficiency issues

7

Exercises

(13)

Ordered Binary Decision Diagrams (OBDDs) [Bryant, ’85]

Canonical representation of Boolean formulas

“If-then-else” binary direct acyclic graphs (DAGs) with one root and two leaves: 1, 0 (or >,⊥; or T, F)

Variable ordering A

₁

, A

₂

, ..., A

_n

imposed a priori.

Paths leading to 1 represent models

Paths leading to 0 represent counter-models Note

Some authors call them Reduced Ordered Binary Decision Diagrams

(ROBDDs)

(14)

Ordered Binary Decision Diagrams (OBDDs) [Bryant, ’85]

Canonical representation of Boolean formulas

“If-then-else” binary direct acyclic graphs (DAGs) with one root and two leaves: 1, 0 (or >,⊥; or T, F)

Variable ordering A

₁

, A

₂

, ..., A

_n

imposed a priori.

Paths leading to 1 represent models

Paths leading to 0 represent counter-models Note

Some authors call them Reduced Ordered Binary Decision Diagrams

(ROBDDs)

(15)

OBDD - Examples

F T

b3 a3

b3 b2 a2

b2

b1 b1

a1 a1

a2

a3 a3 a3

a2

a3

b1 b1 b1 b1 b1 b1

b2 b2 b2 b2

b3 b3

b1 b1

T F

OBDDs of (a

₁

↔ b

₁

) ∧ (a

₂

↔ b

₂

) ∧ (a

₃

↔ b

₃

) with different variable

orderings

(16)

Ordered Decision Trees

Ordered Decision Tree: from root to leaves, variables are encountered always in the same order

Example: Ordered Decision tree for ϕ = (a ∧ b) ∨ (c ∧ d ) a

b

c c

d d d d d d d

c

d b

c

0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1

(17)

From Ordered Decision Trees to OBDD’s: reductions

Recursive applications of the following reductions:

share subnodes: point to the same occurrence of a subtree (via hash consing)

remove redundancies: nodes with same left and right children can

be eliminated (“if A then B else B” =⇒ “B”)

(18)

From Ordered Decision Trees to OBDD’s: reductions

Recursive applications of the following reductions:

share subnodes: point to the same occurrence of a subtree (via hash consing)

remove redundancies: nodes with same left and right children can

be eliminated (“if A then B else B” =⇒ “B”)

(19)

From Ordered Decision Trees to OBDD’s: reductions

Recursive applications of the following reductions:

share subnodes: point to the same occurrence of a subtree (via hash consing)

remove redundancies: nodes with same left and right children can

be eliminated (“if A then B else B” =⇒ “B”)

(20)

Reduction: example

a b

c c

d d d d d d d

c

d b

c

0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1

(21)

Reduction: example

Detect redundacies: a b

c c

d d d d d d d

c

d b

c

0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1

(22)

Reduction: example

Remove redundacies: a b

c c

d d d

c b

c

0 1 0 1 0 1

0 0 0 1 1

(23)

Reduction: example

Remove redundacies: a b

c c

d d d

b c

0 1 0 1 0 1

0 0 0

1

(24)

Reduction: example

Share identical nodes: a b

c c

d d d

b c

0 1 0 1 0 1

0 0 0

1

(25)

Reduction: example

Share identical nodes: a b

c

d

b

0

1

(26)

Reduction: example

Detect redundancies: a b

c

d

b

0

1

(27)

Reduction: example Remove redundancies:

Final OBDD!

a

c

d

b

0

1

(28)

Recursive structure of an OBDD

Assume the variable ordering A

₁

, A

₂

, ..., A

n

:

OBDD(>, {A

₁

, A

₂

, ..., A

n

}) = 1 OBDD(⊥, {A

₁

, A

₂

, ..., A

_n

}) = 0 OBDD(ϕ, {A

₁

, A

₂

, ..., A

_n

}) = if A

₁

then OBDD(ϕ[A

₁

|>], {A

₂

, ..., A

n

})

else OBDD(ϕ[A

₁

|⊥], {A

₂

, ..., A

n

})

(29)

Incrementally building an OBDD

obdd _build (>, {...}) := 1, obdd _build (⊥, {...}) := 0,

obdd _build (A

_i

, {...}) := ite(A

_i

, 1, 0), obdd _build ((¬ϕ), {A

₁

, ..., A

_n

}) :=

apply (¬, obdd _build (ϕ, {A

₁

, ..., A

n

})) obdd _build ((ϕ

₁

op ϕ

₂

), {A

₁

, ..., A

n

}) :=

reduce(

apply ( op,

obdd _build (ϕ

₁

, {A

₁

, ..., A

_n

}), obdd _build (ϕ

₂

, {A

₁

, ..., A

_n

}) ) )

op ∈ {∧, ∨, →, ↔}

“ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

)” is “If A

_i

Then ϕ

^>_i

Else ϕ

^⊥_i

”

(30)

Incrementally building an OBDD

obdd _build (>, {...}) := 1, obdd _build (⊥, {...}) := 0,

obdd _build (A

_i

, {...}) := ite(A

_i

, 1, 0), obdd _build ((¬ϕ), {A

₁

, ..., A

_n

}) :=

apply (¬, obdd _build (ϕ, {A

₁

, ..., A

n

})) obdd _build ((ϕ

₁

op ϕ

₂

), {A

₁

, ..., A

n

}) :=

reduce(

apply ( op,

obdd _build (ϕ

₁

, {A

₁

, ..., A

_n

}), obdd _build (ϕ

₂

, {A

₁

, ..., A

_n

}) ) )

op ∈ {∧, ∨, →, ↔}

“ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

)” is “If A

_i

Then ϕ

^>_i

Else ϕ

^⊥_i

”

(31)

Incrementally building an OBDD

obdd _build (>, {...}) := 1, obdd _build (⊥, {...}) := 0,

obdd _build (A

_i

, {...}) := ite(A

_i

, 1, 0), obdd _build ((¬ϕ), {A

₁

, ..., A

_n

}) :=

apply (¬, obdd _build (ϕ, {A

₁

, ..., A

n

})) obdd _build ((ϕ

₁

op ϕ

₂

), {A

₁

, ..., A

n

}) :=

reduce(

apply ( op,

obdd _build (ϕ

₁

, {A

₁

, ..., A

_n

}), obdd _build (ϕ

₂

, {A

₁

, ..., A

_n

}) ) )

op ∈ {∧, ∨, →, ↔}

“ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

)” is “If A

_i

Then ϕ

^>_i

Else ϕ

^⊥_i

”

(32)

Incrementally building an OBDD

obdd _build (>, {...}) := 1, obdd _build (⊥, {...}) := 0,

obdd _build (A

_i

, {...}) := ite(A

_i

, 1, 0), obdd _build ((¬ϕ), {A

₁

, ..., A

_n

}) :=

apply (¬, obdd _build (ϕ, {A

₁

, ..., A

n

})) obdd _build ((ϕ

₁

op ϕ

₂

), {A

₁

, ..., A

n

}) :=

reduce(

apply ( op,

obdd _build (ϕ

₁

, {A

₁

, ..., A

_n

}), obdd _build (ϕ

₂

, {A

₁

, ..., A

_n

}) ) )

op ∈ {∧, ∨, →, ↔}

“ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

)” is “If A

_i

Then ϕ

^>_i

Else ϕ

^⊥_i

”

(33)

Incrementally building an OBDD

obdd _build (>, {...}) := 1, obdd _build (⊥, {...}) := 0,

obdd _build (A

_i

, {...}) := ite(A

_i

, 1, 0), obdd _build ((¬ϕ), {A

₁

, ..., A

_n

}) :=

apply (¬, obdd _build (ϕ, {A

₁

, ..., A

n

})) obdd _build ((ϕ

₁

op ϕ

₂

), {A

₁

, ..., A

n

}) :=

reduce(

apply ( op,

obdd _build (ϕ

₁

, {A

₁

, ..., A

_n

}), obdd _build (ϕ

₂

, {A

₁

, ..., A

_n

}) ) )

op ∈ {∧, ∨, →, ↔}

“ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

)” is “If A

_i

Then ϕ

^>_i

Else ϕ

^⊥_i

”

(34)

Incrementally building an OBDD (cont.)

apply (op, O

_i

, O

_j

) := (O

_i

op O

_j

) if (O

_i

, O

_j

∈ {1, 0}) apply (¬, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

)) :=

ite(A

_i

, apply (¬, ϕ

^>_i

), apply (¬, ϕ

^⊥_i

))

apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)) :=

if (A

_i

= A

_j

) then ite(A

_i

, apply (op, ϕ

^>_i

, ϕ

^>_j

), apply (op, ϕ

^⊥_i

, ϕ

^⊥_j

))

if (A

_i

< A

_j

) then ite(A

_i

, apply (op, ϕ

^>_i

, ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)),

apply (op, ϕ

^⊥_i

, ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)))

if (A

_i

> A

_j

) then ite(A

_j

, apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ϕ

^>_j

),

apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ϕ

^⊥_j

))

op ∈ {∧, ∨, →, ↔}

(35)

Incrementally building an OBDD (cont.)

apply (op, O

_i

, O

_j

) := (O

_i

op O

_j

) if (O

_i

, O

_j

∈ {1, 0}) apply (¬, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

)) :=

ite(A

_i

, apply (¬, ϕ

^>_i

), apply (¬, ϕ

^⊥_i

))

apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)) :=

if (A

_i

= A

_j

) then ite(A

_i

, apply (op, ϕ

^>_i

, ϕ

^>_j

), apply (op, ϕ

^⊥_i

, ϕ

^⊥_j

))

if (A

_i

< A

_j

) then ite(A

_i

, apply (op, ϕ

^>_i

, ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)),

apply (op, ϕ

^⊥_i

, ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)))

if (A

_i

> A

_j

) then ite(A

_j

, apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ϕ

^>_j

),

apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ϕ

^⊥_j

))

op ∈ {∧, ∨, →, ↔}

(36)

Incrementally building an OBDD (cont.)

apply (op, O

_i

, O

_j

) := (O

_i

op O

_j

) if (O

_i

, O

_j

∈ {1, 0}) apply (¬, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

)) :=

ite(A

_i

, apply (¬, ϕ

^>_i

), apply (¬, ϕ

^⊥_i

))

apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)) :=

if (A

_i

= A

_j

) then ite(A

_i

, apply (op, ϕ

^>_i

, ϕ

^>_j

), apply (op, ϕ

^⊥_i

, ϕ

^⊥_j

))

if (A

_i

< A

_j

) then ite(A

_i

, apply (op, ϕ

^>_i

, ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)),

apply (op, ϕ

^⊥_i

, ite(A

_j

, ϕ

^>_j

, ϕ

^⊥_j

)))

if (A

_i

> A

_j

) then ite(A

_j

, apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ϕ

^>_j

),

apply (op, ite(A

_i

, ϕ

^>_i

, ϕ

^⊥_i

), ϕ

^⊥_j

))

op ∈ {∧, ∨, →, ↔}

(37)

Incrementally building an OBDD (cont.)

Ex: build the obdd for A

₁

∨ A

₂

from those of A

₁

, A

₂

(order: A

₁

, A

₂

):

apply (∨,

A1

z }| {

ite(A

₁

, >, ⊥),

A2

z }| {

ite(A

₂

, >, ⊥))

= ite(A

₁

, apply (∨, >, ite(A

₁

, >, ⊥)), apply (∨, ⊥, ite(A

₂

, >, ⊥)) )

= ite(A

₁

, >, ite(A

₂

, >, ⊥) )

Ex: build the obdd for (A

₁

∨ A

2

) ∧ (A

₁

∨ ¬A

2

) from those of (A

₁

∨ A

₂

), (A

₁

∨ ¬A

₂

) (order: A

₁

, A

₂

):

apply (∧,

(A₁∨A2)

z }| {

ite(A

₁

, >, ite(A

₂

, >, ⊥)),

(A₁∨¬A2)

z }| {

ite(A

₁

, >, ite(A

₂

, ⊥, >)),

= ite(A

₁

, apply (∧, >, >), apply (∧, ite(A

₂

, >, ⊥), ite(A

₂

, ⊥, >))

= ite(A

₁

, >, ite(A

₂

, apply (∧, >, ⊥), apply (∧, ⊥, >)))

= ite(A

₁

, >, ite(A

₂

, ⊥, ⊥))

= ite(A

₁

, >, ⊥)

(38)

Incrementally building an OBDD (cont.)

Ex: build the obdd for A

₁

∨ A

₂

from those of A

₁

, A

₂

(order: A

₁

, A

₂

):

apply (∨,

A1

z }| {

ite(A

₁

, >, ⊥),

A2

z }| {

ite(A

₂

, >, ⊥))

= ite(A

₁

, apply (∨, >, ite(A

₁

, >, ⊥)), apply (∨, ⊥, ite(A

₂

, >, ⊥)) )

= ite(A

₁

, >, ite(A

₂

, >, ⊥) )

Ex: build the obdd for (A

₁

∨ A

2

) ∧ (A

₁

∨ ¬A

2

) from those of (A

₁

∨ A

₂

), (A

₁

∨ ¬A

₂

) (order: A

₁

, A

₂

):

apply (∧,

(A₁∨A2)

z }| {

ite(A

₁

, >, ite(A

₂

, >, ⊥)),

(A₁∨¬A2)

z }| {

ite(A

₁

, >, ite(A

₂

, ⊥, >)),

= ite(A

₁

, apply (∧, >, >), apply (∧, ite(A

₂

, >, ⊥), ite(A

₂

, ⊥, >))

= ite(A

₁

, >, ite(A

₂

, apply (∧, >, ⊥), apply (∧, ⊥, >)))

= ite(A

₁

, >, ite(A

₂

, ⊥, ⊥))

= ite(A

₁

, >, ⊥)

(39)

OBBD incremental building – example

ϕ = (A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

) ∧ (¬A

₁

∨ A

₂

) ∧ (¬A

₁

∨ ¬A

₂

)

(40)

OBBD incremental building – example

ϕ = (A

₁

∨ A

₂

) ∧ (A

₁

∨ ¬A

₂

) ∧ (¬A

₁

∨ A

₂

) ∧ (¬A

₁

∨ ¬A

₂

)

T F

A2 A1

T F

A2 A1

T F

A2 A1

T F

A2 A1

A1

T F

A1

T F

F (A1 v −A2)

(A1 v A2) (−A1 v A2) (−A2 v −A2)

(A1 v A2) ^ (A1 v −A2) (−A1 v A2) ^ (−A1 v −A2)

(A1 v A2) ^ (A1 v −A2) ^ (−A1 v A2) ^ (−A1 v −A2)

(41)

Critical choice of variable Orderings in OBDD’s

(a

₁

↔ b

1

) ∧ (a

₂

↔ b

2

) ∧ (a

₃

↔ b

3

)

Linear size Exponential size

(42)

Critical choice of variable Orderings in OBDD’s

(a

₁

↔ b

1

) ∧ (a

₂

↔ b

2

) ∧ (a

₃

↔ b

3

)

True False

a1

b1

a2

b2 b2

a3

b3 b3

b1

Linear size Exponential size

(43)

Critical choice of variable Orderings in OBDD’s

(a

₁

↔ b

1

) ∧ (a

₂

↔ b

2

) ∧ (a

₃

↔ b

3

)

True False

a1

b1

a2

b2 b2

a3

b3 b3

b1

b1 b1 b1 b1 b1 b1 b1 b1

a3 a3 a3 a3

a2 a2

a1

b3 b3

b2 b2

False True

Linear size Exponential size

(44)

OBDD’s as canonical representation of Boolean formulas

An OBDD is a canonical representation of a Boolean formula:

once the variable ordering is established, equivalent formulas are represented by the same OBDD:

ϕ

₁

↔ ϕ

₂

⇐⇒ OBDD(ϕ

₁

) = OBDD(ϕ

₂

) equivalence check requires constant time!

=⇒validity check requires constant time! (ϕ ↔ >)

=⇒(un)satisfiability check requires constant time! (ϕ ↔ ⊥) the set of the paths from the root to 1 represent all the models of the formula

the set of the paths from the root to 0 represent all the

counter-models of the formula

(45)

OBDD’s as canonical representation of Boolean formulas

An OBDD is a canonical representation of a Boolean formula:

once the variable ordering is established, equivalent formulas are represented by the same OBDD:

ϕ

₁

↔ ϕ

₂

⇐⇒ OBDD(ϕ

₁

) = OBDD(ϕ

₂

) equivalence check requires constant time!

=⇒validity check requires constant time! (ϕ ↔ >)

=⇒(un)satisfiability check requires constant time! (ϕ ↔ ⊥) the set of the paths from the root to 1 represent all the models of the formula

the set of the paths from the root to 0 represent all the

counter-models of the formula

(46)

OBDD’s as canonical representation of Boolean formulas

An OBDD is a canonical representation of a Boolean formula:

once the variable ordering is established, equivalent formulas are represented by the same OBDD:

ϕ

₁

↔ ϕ

₂

⇐⇒ OBDD(ϕ

₁

) = OBDD(ϕ

₂

) equivalence check requires constant time!

=⇒validity check requires constant time! (ϕ ↔ >)

=⇒(un)satisfiability check requires constant time! (ϕ ↔ ⊥) the set of the paths from the root to 1 represent all the models of the formula

the set of the paths from the root to 0 represent all the

counter-models of the formula

(47)

Exponentiality of OBDD’s

The size of OBDD’s may grow exponentially wrt. the number of variables in worst-case

Consequence of the canonicity of OBDD’s (unless P = co-NP) Example: there exist no polynomial-size OBDD representing the electronic circuit of a bitwise multiplier

Note

The size of intermediate OBDD’s may be bigger than that of the final

one (e.g., inconsistent formula)

(48)

Exponentiality of OBDD’s

The size of OBDD’s may grow exponentially wrt. the number of variables in worst-case

Consequence of the canonicity of OBDD’s (unless P = co-NP) Example: there exist no polynomial-size OBDD representing the electronic circuit of a bitwise multiplier

Note

The size of intermediate OBDD’s may be bigger than that of the final

one (e.g., inconsistent formula)

(49)

Exponentiality of OBDD’s

The size of OBDD’s may grow exponentially wrt. the number of variables in worst-case

Consequence of the canonicity of OBDD’s (unless P = co-NP) Example: there exist no polynomial-size OBDD representing the electronic circuit of a bitwise multiplier

Note

The size of intermediate OBDD’s may be bigger than that of the final

one (e.g., inconsistent formula)

(50)

Exponentiality of OBDD’s

The size of OBDD’s may grow exponentially wrt. the number of variables in worst-case

Consequence of the canonicity of OBDD’s (unless P = co-NP) Example: there exist no polynomial-size OBDD representing the electronic circuit of a bitwise multiplier

Note

The size of intermediate OBDD’s may be bigger than that of the final

one (e.g., inconsistent formula)

(51)

Useful Operations over OBDDs

the equivalence check between two OBDDs is simple are they the same OBDD? (=⇒ constant time)

the size of a Boolean composition is up to the product of the size of the operands: |f op g| = O(|f | · |g|)

(but typically much smaller on average).

(52)

Useful Operations over OBDDs

the equivalence check between two OBDDs is simple are they the same OBDD? (=⇒ constant time)

the size of a Boolean composition is up to the product of the size of the operands: |f op g| = O(|f | · |g|)

f g

fg O(|f| |g|)

(but typically much smaller on average).

(53)

Boolean quantification

Shannon’s expansion:

If v is a Boolean variable and f is a Boolean formula, then

∃v .f := f |

_{v =0}

∨ f |

_{v =1}

∀v .f := f |

_{v =0}

∧ f |

_{v =1}

v does no more occur in ∃v .f and ∀v .f !!

Multi-variable quantification: ∃(w

₁

, . . . , w

_n

).f := ∃w

₁

. . . ∃w

_n

.f

Intuition:

µ |= ∃v .f iff exists tvalue ∈ {>, ⊥} s.t. µ ∪ {v := tvalue} |= f µ |= ∀v .f iff forall tvalue ∈ {>, ⊥}, µ ∪ {v := tvalue} |= f Example: ∃b, c . ((a ∧ b) ∨ (c ∧ d )) = a ∨ d

Note

Naive expansion of quantifiers to propositional logic may cause a

blow-up in size of the formulae

(54)

Boolean quantification

Shannon’s expansion:

If v is a Boolean variable and f is a Boolean formula, then

∃v .f := f |

_{v =0}

∨ f |

_{v =1}

∀v .f := f |

_{v =0}

∧ f |

_{v =1}

v does no more occur in ∃v .f and ∀v .f !!

Multi-variable quantification: ∃(w

₁

, . . . , w

_n

).f := ∃w

₁

. . . ∃w

_n

.f

Intuition:

µ |= ∃v .f iff exists tvalue ∈ {>, ⊥} s.t. µ ∪ {v := tvalue} |= f µ |= ∀v .f iff forall tvalue ∈ {>, ⊥}, µ ∪ {v := tvalue} |= f Example: ∃b, c . ((a ∧ b) ∨ (c ∧ d )) = a ∨ d

Note

Naive expansion of quantifiers to propositional logic may cause a

blow-up in size of the formulae

(55)

Boolean quantification

Shannon’s expansion:

If v is a Boolean variable and f is a Boolean formula, then

∃v .f := f |

_{v =0}

∨ f |

_{v =1}

∀v .f := f |

_{v =0}

∧ f |

_{v =1}

v does no more occur in ∃v .f and ∀v .f !!

Multi-variable quantification: ∃(w

₁

, . . . , w

_n

).f := ∃w

₁

. . . ∃w

_n

.f Intuition:

µ |= ∃v .f iff exists tvalue ∈ {>, ⊥} s.t. µ ∪ {v := tvalue} |= f µ |= ∀v .f iff forall tvalue ∈ {>, ⊥}, µ ∪ {v := tvalue} |= f Example: ∃b, c . ((a ∧ b) ∨ (c ∧ d )) = a ∨ d

Note

Naive expansion of quantifiers to propositional logic may cause a

blow-up in size of the formulae

(56)

Boolean quantification

Shannon’s expansion:

If v is a Boolean variable and f is a Boolean formula, then

∃v .f := f |

_{v =0}

∨ f |

_{v =1}

∀v .f := f |

_{v =0}

∧ f |

_{v =1}

v does no more occur in ∃v .f and ∀v .f !!

Multi-variable quantification: ∃(w

₁

, . . . , w

_n

).f := ∃w

₁

. . . ∃w

_n

.f Intuition:

µ |= ∃v .f iff exists tvalue ∈ {>, ⊥} s.t. µ ∪ {v := tvalue} |= f µ |= ∀v .f iff forall tvalue ∈ {>, ⊥}, µ ∪ {v := tvalue} |= f Example: ∃b, c . ((a ∧ b) ∨ (c ∧ d )) = a ∨ d

Note

Naive expansion of quantifiers to propositional logic may cause a

blow-up in size of the formulae

(57)

Boolean quantification

Shannon’s expansion:

If v is a Boolean variable and f is a Boolean formula, then

∃v .f := f |

_{v =0}

∨ f |

_{v =1}

∀v .f := f |

_{v =0}

∧ f |

_{v =1}

v does no more occur in ∃v .f and ∀v .f !!

Multi-variable quantification: ∃(w

₁

, . . . , w

_n

).f := ∃w

₁

. . . ∃w

_n

.f Intuition:

µ |= ∃v .f iff exists tvalue ∈ {>, ⊥} s.t. µ ∪ {v := tvalue} |= f µ |= ∀v .f iff forall tvalue ∈ {>, ⊥}, µ ∪ {v := tvalue} |= f Example: ∃b, c . ((a ∧ b) ∨ (c ∧ d )) = a ∨ d

Note

Naive expansion of quantifiers to propositional logic may cause a

blow-up in size of the formulae

(58)

Boolean quantification

Shannon’s expansion:

If v is a Boolean variable and f is a Boolean formula, then

∃v .f := f |

_{v =0}

∨ f |

_{v =1}

∀v .f := f |

_{v =0}

∧ f |

_{v =1}

v does no more occur in ∃v .f and ∀v .f !!

Multi-variable quantification: ∃(w

₁

, . . . , w

_n

).f := ∃w

₁

. . . ∃w

_n

.f Intuition:

µ |= ∃v .f iff exists tvalue ∈ {>, ⊥} s.t. µ ∪ {v := tvalue} |= f µ |= ∀v .f iff forall tvalue ∈ {>, ⊥}, µ ∪ {v := tvalue} |= f Example: ∃b, c . ((a ∧ b) ∨ (c ∧ d )) = a ∨ d

Note

Naive expansion of quantifiers to propositional logic may cause a

blow-up in size of the formulae

(59)

OBDD’s and Boolean quantification

OBDD’s handle quantification operations quite efficiently

if f is a sub-OBDD labeled by variable v , then f |

_{v =1}

and f |

_{v =0}

are the “then” and “else” branches of f

fv=1 fv=0

. . . . v

=⇒ lots of sharing of subformulae!

(60)

OBDD – summary

Factorize common parts of the search tree (DAG) Require setting a variable ordering a priori (critical!) Canonical representation of a Boolean formula.

Once built, logical operations (satisfiability, validity, equivalence) immediate.

Represents all models and counter-models of the formula.

Require exponential space in worst-case

Very efficient for some practical problems (circuits, symbolic

model checking).

(61)

Outline

1

Motivations

2

Ordered Binary Decision Diagrams

3

Symbolic representation of systems

4

Symbolic CTL Model Checking

5

A simple example

6

Symbolic CTL M.C: efficiency issues

7

Exercises

(62)

Symbolic Representation of Kripke Structures

Symbolic representation:

sets of states as their characteristic function (Boolean formula) provide logical representation and transformations of characteristic functions

Example:

three state variables x

1

, x

2

, x

3

:

{ 000, 001, 010, 011 } represented as “first bit false”: ¬x

₁

with five state variables x

1

, x

2

, x

3

, x

4

, x

5

:

{ 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111,. . . ,

01111 } still represented as “first bit false”: ¬x

₁

(63)

Symbolic Representation of Kripke Structures

Symbolic representation:

sets of states as their characteristic function (Boolean formula) provide logical representation and transformations of characteristic functions

Example:

three state variables x

1

, x

2

, x

3

:

{ 000, 001, 010, 011 } represented as “first bit false”: ¬x

₁

with five state variables x

1

, x

2

, x

3

, x

4

, x

5

:

{ 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111,. . . ,

01111 } still represented as “first bit false”: ¬x

₁

(64)

Symbolic Representation of Kripke Structures

Symbolic representation:

sets of states as their characteristic function (Boolean formula) provide logical representation and transformations of characteristic functions

Example:

three state variables x

1

, x

2

, x

3

:

{ 000, 001, 010, 011 } represented as “first bit false”: ¬x

₁

with five state variables x

1

, x

2

, x

3

, x

4

, x

5

:

{ 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111,. . . ,

01111 } still represented as “first bit false”: ¬x

₁

(65)

Kripke Structures in Propositional Logic

Let M = (S, I, R, L, AF ) be a Kripke structure

States s ∈ S are described by means of an array V of Boolean state variables.

A state is a truth assignment to each atomic proposition in V.

0100 is represented by the formula (¬x

1

∧ x

₂

∧ ¬x

₃

∧ ¬x

₄

) we call ξ(s) the formula representing the state s ∈ S (Intuition: ξ(s) holds iff the system is in the state s)

A set of states Q ⊆ S can be represented by (any formula which is logically equivalent to) the formula ξ(Q):

_

s∈Q

ξ(s)

(Intuition: ξ(Q) holds iff the system is in one of the states s ∈ Q)

Bijection between models of ξ(Q) and states in Q

(66)

Kripke Structures in Propositional Logic

Let M = (S, I, R, L, AF ) be a Kripke structure

States s ∈ S are described by means of an array V of Boolean state variables.

A state is a truth assignment to each atomic proposition in V.

0100 is represented by the formula (¬x

1

∧ x

₂

∧ ¬x

₃

∧ ¬x

₄

) we call ξ(s) the formula representing the state s ∈ S (Intuition: ξ(s) holds iff the system is in the state s)

A set of states Q ⊆ S can be represented by (any formula which is logically equivalent to) the formula ξ(Q):

_

s∈Q

ξ(s)

(Intuition: ξ(Q) holds iff the system is in one of the states s ∈ Q)

Bijection between models of ξ(Q) and states in Q

(67)

Kripke Structures in Propositional Logic

Let M = (S, I, R, L, AF ) be a Kripke structure

States s ∈ S are described by means of an array V of Boolean state variables.

A state is a truth assignment to each atomic proposition in V.

0100 is represented by the formula (¬x

1

∧ x

₂

∧ ¬x

₃

∧ ¬x

₄

) we call ξ(s) the formula representing the state s ∈ S (Intuition: ξ(s) holds iff the system is in the state s)

A set of states Q ⊆ S can be represented by (any formula which is logically equivalent to) the formula ξ(Q):

_

s∈Q

ξ(s)

(Intuition: ξ(Q) holds iff the system is in one of the states s ∈ Q)

Bijection between models of ξ(Q) and states in Q

(68)

Kripke Structures in Propositional Logic

Let M = (S, I, R, L, AF ) be a Kripke structure

States s ∈ S are described by means of an array V of Boolean state variables.

A state is a truth assignment to each atomic proposition in V.

0100 is represented by the formula (¬x

1

∧ x

₂

∧ ¬x

₃

∧ ¬x

₄

) we call ξ(s) the formula representing the state s ∈ S (Intuition: ξ(s) holds iff the system is in the state s)

A set of states Q ⊆ S can be represented by (any formula which is logically equivalent to) the formula ξ(Q):

_

s∈Q

ξ(s)

(Intuition: ξ(Q) holds iff the system is in one of the states s ∈ Q)

Bijection between models of ξ(Q) and states in Q

(69)

Kripke Structures in Propositional Logic

Let M = (S, I, R, L, AF ) be a Kripke structure

States s ∈ S are described by means of an array V of Boolean state variables.

A state is a truth assignment to each atomic proposition in V.

0100 is represented by the formula (¬x

1

∧ x

₂

∧ ¬x

₃

∧ ¬x

₄

) we call ξ(s) the formula representing the state s ∈ S (Intuition: ξ(s) holds iff the system is in the state s)

A set of states Q ⊆ S can be represented by (any formula which is logically equivalent to) the formula ξ(Q):

_

s∈Q

ξ(s)

(Intuition: ξ(Q) holds iff the system is in one of the states s ∈ Q)

Bijection between models of ξ(Q) and states in Q

(70)

Kripke Structures in Propositional Logic

Let M = (S, I, R, L, AF ) be a Kripke structure

States s ∈ S are described by means of an array V of Boolean state variables.

A state is a truth assignment to each atomic proposition in V.

0100 is represented by the formula (¬x

1

∧ x

₂

∧ ¬x

₃

∧ ¬x

₄

) we call ξ(s) the formula representing the state s ∈ S (Intuition: ξ(s) holds iff the system is in the state s)

A set of states Q ⊆ S can be represented by (any formula which is logically equivalent to) the formula ξ(Q):

_

s∈Q

ξ(s)

(Intuition: ξ(Q) holds iff the system is in one of the states s ∈ Q)

Bijection between models of ξ(Q) and states in Q

(71)

Kripke Structures in Propositional Logic

Let M = (S, I, R, L, AF ) be a Kripke structure

States s ∈ S are described by means of an array V of Boolean state variables.

A state is a truth assignment to each atomic proposition in V.

0100 is represented by the formula (¬x

1

∧ x

₂

∧ ¬x

₃

∧ ¬x

₄

) we call ξ(s) the formula representing the state s ∈ S (Intuition: ξ(s) holds iff the system is in the state s)

A set of states Q ⊆ S can be represented by (any formula which is logically equivalent to) the formula ξ(Q):

_

s∈Q

ξ(s)

(Intuition: ξ(Q) holds iff the system is in one of the states s ∈ Q)

Bijection between models of ξ(Q) and states in Q

(72)

Remark

every propositional formula is a (typically very compact) representation of the set of assignments satisfying it Any formula equivalent to ξ(Q) is a representation of Q

=⇒ Typically Q can be encoded by much smaller formulas than W

s∈Q

ξ(s)!

Example: Q ={ 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111,. . . , 01111 } represented as “first bit false”: ¬x

1

W

s∈Q

ξ(s) = (¬x

₁

∧ ¬x

₂

∧ ¬x

₃

∧ ¬x

₄

∧ ¬x

5

) ∨ (¬x

₁

∧ ¬x

2

∧ ¬x

3

∧ ¬x

4

∧ x

5

) ∨ (¬x

₁

∧ ¬x

2

∧ ¬x

3

∧ x

4

∧ ¬x

5

) ∨ ...

(¬x

₁

∧ x

₂

∧ x

₃

∧ x

₄

∧ x

₅

)



 



 



2

⁴

disjuncts

(73)

Remark

every propositional formula is a (typically very compact) representation of the set of assignments satisfying it Any formula equivalent to ξ(Q) is a representation of Q

=⇒ Typically Q can be encoded by much smaller formulas than W

s∈Q

ξ(s)!

Example: Q ={ 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111,. . . , 01111 } represented as “first bit false”: ¬x

1

W

s∈Q

ξ(s) = (¬x

₁

∧ ¬x

₂

∧ ¬x

₃

∧ ¬x

₄

∧ ¬x

5

) ∨ (¬x

₁

∧ ¬x

2

∧ ¬x

3

∧ ¬x

4

∧ x

5

) ∨ (¬x

₁

∧ ¬x

2

∧ ¬x

3

∧ x

4

∧ ¬x

5

) ∨ ...

(¬x

₁

∧ x

₂

∧ x

₃

∧ x

₄

∧ x

₅

)



 



 



2

⁴

disjuncts

(74)

Remark

every propositional formula is a (typically very compact) representation of the set of assignments satisfying it Any formula equivalent to ξ(Q) is a representation of Q

=⇒ Typically Q can be encoded by much smaller formulas than W

s∈Q

ξ(s)!

Example: Q ={ 00000, 00001, 00010, 00011, 00100, 00101, 00110, 00111,. . . , 01111 } represented as “first bit false”: ¬x

1

W

s∈Q

ξ(s) = (¬x

₁

∧ ¬x

₂

∧ ¬x

₃

∧ ¬x

₄

∧ ¬x

5

) ∨ (¬x

₁

∧ ¬x

2

∧ ¬x

3

∧ ¬x

4

∧ x

5

) ∨ (¬x

₁

∧ ¬x

2

∧ ¬x

3

∧ x

4

∧ ¬x

5

) ∨ ...

(¬x

₁

∧ x

₂

∧ x

₃

∧ x

₄

∧ x

₅

)



 



 



2

⁴

disjuncts

(75)

Symbolic Representation of Set Operators

One-to-one correspondence between sets and Boolean operators Set of all the states: ξ(S) := >

Empty set : ξ(∅) := ⊥

Union represented by disjunction:

ξ(P ∪ Q) := ξ(P) ∨ ξ(Q)

Intersection represented by conjunction:

ξ(P ∩ Q) := ξ(P) ∧ ξ(Q)

Complement represented by negation:

ξ(S/P) := ¬ξ(P)

(76)

Symbolic Representation of Set Operators

One-to-one correspondence between sets and Boolean operators Set of all the states: ξ(S) := >

Empty set : ξ(∅) := ⊥

Union represented by disjunction:

ξ(P ∪ Q) := ξ(P) ∨ ξ(Q)

Intersection represented by conjunction:

ξ(P ∩ Q) := ξ(P) ∧ ξ(Q)

Complement represented by negation:

ξ(S/P) := ¬ξ(P)

(77)

Symbolic Representation of Set Operators

One-to-one correspondence between sets and Boolean operators Set of all the states: ξ(S) := >

Empty set : ξ(∅) := ⊥

Union represented by disjunction:

ξ(P ∪ Q) := ξ(P) ∨ ξ(Q)

Intersection represented by conjunction:

ξ(P ∩ Q) := ξ(P) ∧ ξ(Q)

Complement represented by negation:

ξ(S/P) := ¬ξ(P)

(78)

Symbolic Representation of Set Operators

One-to-one correspondence between sets and Boolean operators Set of all the states: ξ(S) := >

Empty set : ξ(∅) := ⊥

Union represented by disjunction:

ξ(P ∪ Q) := ξ(P) ∨ ξ(Q)

Intersection represented by conjunction:

ξ(P ∩ Q) := ξ(P) ∧ ξ(Q)

Complement represented by negation:

ξ(S/P) := ¬ξ(P)

(79)

Symbolic Representation of Set Operators

One-to-one correspondence between sets and Boolean operators Set of all the states: ξ(S) := >

Empty set : ξ(∅) := ⊥

Union represented by disjunction:

ξ(P ∪ Q) := ξ(P) ∨ ξ(Q)

Intersection represented by conjunction:

ξ(P ∩ Q) := ξ(P) ∧ ξ(Q)

Complement represented by negation:

ξ(S/P) := ¬ξ(P)

(80)

Symbolic Representation of Set Operators

One-to-one correspondence between sets and Boolean operators Set of all the states: ξ(S) := >

Empty set : ξ(∅) := ⊥

Union represented by disjunction:

ξ(P ∪ Q) := ξ(P) ∨ ξ(Q)

Intersection represented by conjunction:

ξ(P ∩ Q) := ξ(P) ∧ ξ(Q)

Complement represented by negation:

ξ(S/P) := ¬ξ(P)

(81)

Symbolic Representation of Transition Relations

The transition relation R is a set of pairs of states: R ⊆ S × S A transition is a pair of states (s, s

⁰

)

A new vector of variables V’ (the next state vector) represents the value of variables after the transition has occurred

ξ(s, s

⁰

) defined as ξ(s) ∧ ξ(s

⁰

) (Intuition: ξ(s, s

⁰

) holds iff the system is in the state s and moves to state s

⁰

in next step) The transition relation R can be (naively) represented by

_

(s,s⁰)∈R

ξ(s, s

⁰

) = _

(s,s⁰)∈R

(ξ(s) ∧ ξ(s

⁰

))

Note

Each formula equivalent to ξ(R) is a representation of R

=⇒ Typically R can be encoded by a much smaller formula than W

(s,s⁰)∈R

ξ(s) ∧ ξ(s

⁰

)!

(82)

Symbolic Representation of Transition Relations

The transition relation R is a set of pairs of states: R ⊆ S × S A transition is a pair of states (s, s

⁰

)

A new vector of variables V’ (the next state vector) represents the value of variables after the transition has occurred

ξ(s, s

⁰

) defined as ξ(s) ∧ ξ(s

⁰

) (Intuition: ξ(s, s

⁰

) holds iff the system is in the state s and moves to state s

⁰

in next step) The transition relation R can be (naively) represented by

_

(s,s⁰)∈R

ξ(s, s

⁰

) = _

(s,s⁰)∈R

(ξ(s) ∧ ξ(s

⁰

))

Note

Each formula equivalent to ξ(R) is a representation of R

=⇒ Typically R can be encoded by a much smaller formula than W

(s,s⁰)∈R

ξ(s) ∧ ξ(s

⁰

)!

(83)

Symbolic Representation of Transition Relations

The transition relation R is a set of pairs of states: R ⊆ S × S A transition is a pair of states (s, s

⁰

)

A new vector of variables V’ (the next state vector) represents the value of variables after the transition has occurred

ξ(s, s

⁰

) defined as ξ(s) ∧ ξ(s

⁰

) (Intuition: ξ(s, s

⁰

) holds iff the system is in the state s and moves to state s

⁰

in next step) The transition relation R can be (naively) represented by

_

(s,s⁰)∈R

ξ(s, s

⁰

) = _

(s,s⁰)∈R

(ξ(s) ∧ ξ(s

⁰

))

Note

Each formula equivalent to ξ(R) is a representation of R

=⇒ Typically R can be encoded by a much smaller formula than W

(s,s⁰)∈R

ξ(s) ∧ ξ(s

⁰

)!

(84)

Symbolic Representation of Transition Relations

The transition relation R is a set of pairs of states: R ⊆ S × S A transition is a pair of states (s, s

⁰

)

A new vector of variables V’ (the next state vector) represents the value of variables after the transition has occurred

ξ(s, s

⁰

) defined as ξ(s) ∧ ξ(s

⁰

) (Intuition: ξ(s, s

⁰

) holds iff the system is in the state s and moves to state s

⁰

in next step) The transition relation R can be (naively) represented by

_

(s,s⁰)∈R

ξ(s, s

⁰

) = _

(s,s⁰)∈R

(ξ(s) ∧ ξ(s

⁰

))

Note

Each formula equivalent to ξ(R) is a representation of R

=⇒ Typically R can be encoded by a much smaller formula than W

(s,s⁰)∈R

ξ(s) ∧ ξ(s

⁰

)!

(85)

Symbolic Representation of Transition Relations

The transition relation R is a set of pairs of states: R ⊆ S × S A transition is a pair of states (s, s

⁰

)

A new vector of variables V’ (the next state vector) represents the value of variables after the transition has occurred

ξ(s, s

⁰

) defined as ξ(s) ∧ ξ(s

⁰

) (Intuition: ξ(s, s

⁰

) holds iff the system is in the state s and moves to state s

⁰

in next step) The transition relation R can be (naively) represented by

_

(s,s⁰)∈R

ξ(s, s

⁰

) = _

(s,s⁰)∈R

(ξ(s) ∧ ξ(s

⁰

))

Note

Each formula equivalent to ξ(R) is a representation of R

=⇒ Typically R can be encoded by a much smaller formula than W

(s,s⁰)∈R

ξ(s) ∧ ξ(s

⁰

)!

(86)

Symbolic Representation of Transition Relations

The transition relation R is a set of pairs of states: R ⊆ S × S A transition is a pair of states (s, s

⁰

)

A new vector of variables V’ (the next state vector) represents the value of variables after the transition has occurred

ξ(s, s

⁰

) defined as ξ(s) ∧ ξ(s

⁰

) (Intuition: ξ(s, s

⁰

) holds iff the system is in the state s and moves to state s

⁰

in next step) The transition relation R can be (naively) represented by

_

(s,s⁰)∈R

ξ(s, s

⁰

) = _

(s,s⁰)∈R

(ξ(s) ∧ ξ(s

⁰

))

Note

Each formula equivalent to ξ(R) is a representation of R

=⇒ Typically R can be encoded by a much smaller formula than W

(s,s⁰)∈R

ξ(s) ∧ ξ(s

⁰

)!

(87)

Example: a simple counter

MODULE main VAR

v0 : boolean;

v1 : boolean;

out : 0..3;

ASSIGN

init(v0) := 0;

next(v0) := !v0;

init(v1) := 0;

next(v1) := (v0 xor v1);

out := toint(v0) + 2*toint(v1);

v₀

v1

v

1

v

0

v

₁⁰

v

₀⁰

0 0 0 1

0 1 1 0

1 0 1 1

1 1 0 0

00

11 01

10

(88)

Symbolic representation of systems

Example: a simple counter [cont.]

v₀

v1

v

1

v

0

v

₁⁰

v

₀⁰

0 0 0 1

0 1 1 0

1 0 1 1

1 1 0 0

00

11 01

10

ξ(R) = (v

₀

↔ ¬v

0

) ∧ (v

₁

↔ v

0

L v

₁

) W

(s,s⁰)∈R

ξ(s) ∧ ξ(s

⁰

) = (¬v

₁

∧ ¬v

₀

∧ ¬v

₁⁰

∧ v

₀⁰

) ∨

(¬v

₁

∧ v

₀

∧ v

₁⁰

∧ ¬v

₀⁰

) ∨

(v

₁

∧ ¬v

0

∧ v

₁⁰

∧ v

₀⁰

) ∨

(v

₁

∧ v

₀

∧ ¬v

₁⁰

∧ ¬v

₀⁰

)

(89)

Symbolic representation of systems

Example: a simple counter [cont.]

v₀

v1

v

1

v

0

v

₁⁰

v

₀⁰

0 0 0 1

0 1 1 0

1 0 1 1

1 1 0 0

00

11 01

10

ξ(R) = (v

₀⁰

↔ ¬v

0

) ∧ (v

₁⁰

↔ v

0

L v

₁

)

(s,s⁰)∈R

ξ(s) ∧ ξ(s ) = (¬v

₁

∧ ¬v

₀

∧ ¬v

₁

∧ v

₀

) ∨

(¬v

₁

∧ v

₀

∧ v

₁⁰

∧ ¬v

₀⁰

) ∨

(v

₁

∧ ¬v

0

∧ v

₁⁰

∧ v

₀⁰

) ∨

(v

₁

∧ v

₀

∧ ¬v

₁⁰

∧ ¬v

₀⁰

)

(90)

Example: a simple counter [cont.]

v₀

v1

v

1

v

0

v

₁⁰

v

₀⁰

0 0 0 1

0 1 1 0

1 0 1 1

1 1 0 0

00

11 01

10

ξ(R) = (v

₀⁰

↔ ¬v

0

) ∧ (v

₁⁰

↔ v

0

L v

₁

) W

(s,s⁰)∈R

ξ(s) ∧ ξ(s

⁰

) = (¬v

₁

∧ ¬v

₀

∧ ¬v

₁⁰

∧ v

₀⁰

) ∨

(¬v

₁

∧ v

₀

∧ v

₁⁰

∧ ¬v

₀⁰

) ∨

(v

₁

∧ ¬v

0

∧ v

₁⁰

∧ v

₀⁰

) ∨

(v

₁

∧ v

₀

∧ ¬v

₁⁰

∧ ¬v

₀⁰

)