Introduction to Formal Methods Chapter 07: LTL Symbolic Model Checking

Introduction to Formal Methods

Chapter 07: LTL Symbolic 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

May, 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.

Outline

1 The problem

2 The general algorithm Compute the tableau T _ψ Compute the product M × T _ψ Check the emptiness of L(M × T _ψ )

3 An example

4 Exercises

Outline

1 The problem

2 The general algorithm Compute the tableau T _ψ Compute the product M × T _ψ Check the emptiness of L(M × T _ψ )

3 An example

4 Exercises

The problem

Given a Kripke structure M and an LTL specification ϕ, does M satisfy ϕ?:

M |= ϕ

Equivalent to the CTL ^∗ M.C. problem:

M |= Aϕ

Dual CTL ^∗ M.C. problem:

M |= E¬ϕ

The problem

Given a Kripke structure M and an LTL specification ϕ, does M satisfy ϕ?:

M |= ϕ

Equivalent to the CTL ^∗ M.C. problem:

M |= Aϕ

Dual CTL ^∗ M.C. problem:

M |= E¬ϕ

The problem

Given a Kripke structure M and an LTL specification ϕ, does M satisfy ϕ?:

M |= ϕ

Equivalent to the CTL ^∗ M.C. problem:

M |= Aϕ

Dual CTL ^∗ M.C. problem:

M |= E¬ϕ

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C.

Let M be a Kripke model and ϕ be an LTL formula:

M |= Aϕ (CTL ^∗ )

⇐⇒ M |= ϕ (LTL)

⇐⇒ L(M) ⊆ L(ϕ)

⇐⇒ L(M) ∩ L(ϕ) = ∅

⇐⇒ L(M) ∩ L(¬ϕ) = ∅

⇐⇒ L(M) ∩ L(T ¬ϕ ) = ∅

⇐⇒ L(M × T ¬ϕ ) = ∅

⇐⇒ M × T ¬ϕ 6|= EGtrue

T ¬ϕ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy ¬ϕ (do not satisfy ϕ)

=⇒ M × T ¬ϕ represents all and only the paths appearing in M and not

in ϕ.

LTL Symbolic M.C. (dual version)

Let M be a Kripke model and ψ = ¬ϕ ^def be an LTL formula:

M |= Eψ

⇐⇒ M 6|= A¬ψ

⇐⇒ ...

⇐⇒ L(M × T ψ ) 6= ∅

⇐⇒ M × T ψ |= EGtrue

T _ψ is a fair Kripke structure, called Tableau, which represents all and only the paths that satisfy the LTL formula ψ

=⇒ M × T _ψ represents all and only the paths appearing in both M and

T _ψ .

LTL Symbolic Model Checking

Three steps:

(i) Compute the tableau T _ψ (T _ψ is a fair Kripke structure) (ii) Compute the product M × T _ψ

(M × T _ψ is a fair Kripke structure) (iii) Check the emptiness of L(M × T _ψ )

(e.i., check that M × T _ψ 6|= EGTrue)

LTL Symbolic Model Checking

Three steps:

(i) Compute the tableau T _ψ (T _ψ is a fair Kripke structure) (ii) Compute the product M × T _ψ

(M × T _ψ is a fair Kripke structure) (iii) Check the emptiness of L(M × T _ψ )

(e.i., check that M × T _ψ 6|= EGTrue)

LTL Symbolic Model Checking

Three steps:

(i) Compute the tableau T _ψ (T _ψ is a fair Kripke structure) (ii) Compute the product M × T _ψ

(M × T _ψ is a fair Kripke structure) (iii) Check the emptiness of L(M × T _ψ )

(e.i., check that M × T _ψ 6|= EGTrue)

LTL Symbolic Model Checking

Three steps:

(i) Compute the tableau T _ψ (T _ψ is a fair Kripke structure) (ii) Compute the product M × T _ψ

(M × T _ψ is a fair Kripke structure) (iii) Check the emptiness of L(M × T _ψ )

(e.i., check that M × T _ψ 6|= EGTrue)

Outline

1 The problem

2 The general algorithm Compute the tableau T _ψ Compute the product M × T _ψ Check the emptiness of L(M × T _ψ )

3 An example

4 Exercises

Outline

1 The problem

2 The general algorithm Compute the tableau T _ψ Compute the product M × T _ψ Check the emptiness of L(M × T _ψ )

3 An example

4 Exercises

Building the tableau T ψ for ψ: the set of states

Elementary subformulas of ψ: el(ψ) el(p) := {p}

el(¬ϕ 1 ) := el(ϕ 1 )

el(ϕ 1 ∧ ϕ ₂ ) := el(ϕ 1 ) ∪ el(ϕ 2 ) el(Xϕ 1 ) = {Xϕ 1 } ∪ el(ϕ ₁ )

el(ϕ 1 Uϕ 2 ) := {X(ϕ 1 Uϕ 2 )} ∪ el(ϕ 1 ) ∪ el(ϕ 2 )

Intuition: el(ψ) is the set of propositions and X-formulas occurring ψ ⁰ , ψ ⁰ being the result of applying recursively the tableau

expansion rules to ψ

The set of states S _{T ψ} of T _ψ is given by 2 ^el(ψ)

The labeling function L _{T ψ} of T _ψ comes straightforwardly

(the label is the Boolean component of each state)

Building the tableau T ψ for ψ: the set of states

Elementary subformulas of ψ: el(ψ) el(p) := {p}

el(¬ϕ 1 ) := el(ϕ 1 )

el(ϕ 1 ∧ ϕ ₂ ) := el(ϕ 1 ) ∪ el(ϕ 2 ) el(Xϕ 1 ) = {Xϕ 1 } ∪ el(ϕ ₁ )

el(ϕ 1 Uϕ 2 ) := {X(ϕ 1 Uϕ 2 )} ∪ el(ϕ 1 ) ∪ el(ϕ 2 )

Intuition: el(ψ) is the set of propositions and X-formulas occurring ψ ⁰ , ψ ⁰ being the result of applying recursively the tableau

expansion rules to ψ

The set of states S _{T ψ} of T _ψ is given by 2 ^el(ψ)

The labeling function L _{T ψ} of T _ψ comes straightforwardly

(the label is the Boolean component of each state)

Building the tableau T ψ for ψ: the set of states

Elementary subformulas of ψ: el(ψ) el(p) := {p}

el(¬ϕ 1 ) := el(ϕ 1 )

el(ϕ 1 ∧ ϕ ₂ ) := el(ϕ 1 ) ∪ el(ϕ 2 ) el(Xϕ 1 ) = {Xϕ 1 } ∪ el(ϕ ₁ )

el(ϕ 1 Uϕ 2 ) := {X(ϕ 1 Uϕ 2 )} ∪ el(ϕ 1 ) ∪ el(ϕ 2 )

Intuition: el(ψ) is the set of propositions and X-formulas occurring ψ ⁰ , ψ ⁰ being the result of applying recursively the tableau

expansion rules to ψ

The set of states S _{T ψ} of T _ψ is given by 2 ^el(ψ)

The labeling function L _{T ψ} of T _ψ comes straightforwardly

(the label is the Boolean component of each state)

Building the tableau T ψ for ψ: the set of states

Elementary subformulas of ψ: el(ψ) el(p) := {p}

el(¬ϕ 1 ) := el(ϕ 1 )

el(ϕ 1 ∧ ϕ ₂ ) := el(ϕ 1 ) ∪ el(ϕ 2 ) el(Xϕ 1 ) = {Xϕ 1 } ∪ el(ϕ ₁ )

el(ϕ 1 Uϕ 2 ) := {X(ϕ 1 Uϕ 2 )} ∪ el(ϕ 1 ) ∪ el(ϕ 2 )

Intuition: el(ψ) is the set of propositions and X-formulas occurring ψ ⁰ , ψ ⁰ being the result of applying recursively the tableau

expansion rules to ψ

The set of states S _{T ψ} of T _ψ is given by 2 ^el(ψ)

The labeling function L _{T ψ} of T _ψ comes straightforwardly

(the label is the Boolean component of each state)

Example: ψ := pUq

el(pUq) = el((q ∨ (p ∧ X(pUq))) = {p, q, X(pUq)}

=⇒ S _{T ψ} = {

1 : {p, q, X(pUq)}, [pUq]

2 : {¬p, q, X(pUq)}, [pUq]

3 : {p, ¬q, X(pUq)}, [pUq]

4 : {¬p, q, ¬X(pUq)}, [pUq]

5 : {¬p, ¬q, X(pUq)}, [¬pUq]

6 : {p, q, ¬X(pUq)}, [pUq]

7 : {p, ¬q, ¬X(pUq)}, [¬pUq]

8 : {¬p, ¬q, ¬X(pUq)} [¬pUq]

}

Example: ψ := pUq

el(pUq) = el((q ∨ (p ∧ X(pUq))) = {p, q, X(pUq)}

=⇒ S _{T ψ} = {

1 : {p, q, X(pUq)}, [pUq]

2 : {¬p, q, X(pUq)}, [pUq]

3 : {p, ¬q, X(pUq)}, [pUq]

4 : {¬p, q, ¬X(pUq)}, [pUq]

5 : {¬p, ¬q, X(pUq)}, [¬pUq]

6 : {p, q, ¬X(pUq)}, [pUq]

7 : {p, ¬q, ¬X(pUq)}, [¬pUq]

8 : {¬p, ¬q, ¬X(pUq)} [¬pUq]

}

Example: ψ := pUq [cont.]

Xψ Xψ Xψ

−Xψ Xψ −Xψ

−Xψ −Xψ

3

4

5 6

7 8

2

1 p q −p p −q

−p q −p −q p q

p −q −p −q

q

Building the tableau T ψ for ψ: sat()

Set of states in S _{T ψ} satisfying ϕ _i : sat(ϕ _i ) sat(ϕ 1 ) := {s | ϕ 1 ∈ s}, ϕ ₁ ∈ el(ψ) sat(¬ϕ 1 ) := S T

/sat(ϕ 1 )

sat(ϕ 1 ∧ ϕ ₂ ) := sat(ϕ 1 ) ∩ sat(ϕ 2 )

sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∪ (sat(ϕ 1 ) ∩ sat(X(ϕ 1 Uϕ 2 )))

intuition: sat() establishes in which states subformulas are true

Building the tableau T ψ for ψ: sat()

Set of states in S _{T ψ} satisfying ϕ _i : sat(ϕ _i ) sat(ϕ 1 ) := {s | ϕ 1 ∈ s}, ϕ ₁ ∈ el(ψ) sat(¬ϕ 1 ) := S T

/sat(ϕ 1 )

sat(ϕ 1 ∧ ϕ ₂ ) := sat(ϕ 1 ) ∩ sat(ϕ 2 )

sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∪ (sat(ϕ 1 ) ∩ sat(X(ϕ 1 Uϕ 2 )))

intuition: sat() establishes in which states subformulas are true

Example: ψ := pUq [cont.]

Xψ Xψ Xψ

−Xψ Xψ −Xψ

−Xψ −Xψ

3

4

5 6

7 8

2

1 p q −p p −q

−p q −p −q p q

p −q −p −q

q

ψ ψ ψ

ψ −ψ ψ

−ψ −ψ

Building the tableau T ψ for ψ: initial states and transition relation

Set of states in S _{T ψ} satisfying ϕ _i : sat(ϕ _i ) sat(ϕ ₁ ) := {s | ϕ ₁ ∈ s}, ϕ ₁ ∈ el(ψ) sat(¬ϕ 1 ) := S T

/sat(ϕ 1 )

sat(ϕ 1 ∧ ϕ ₂ ) := sat(ϕ 1 ) ∩ sat(ϕ 2 )

sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∪ (sat(ϕ 1 ) ∩ sat(X(ϕ 1 Uϕ 2 )))

Intuition: sat() establishes in which states subformulas are true The set of initial states I _{T ψ} is defined as

I _{T ψ} = sat(ψ)

The transition relation R _{T ψ} is defined as R _{T ψ} (s, s ⁰ ) = \

Xϕ _i ∈el(ψ)

(s, s ⁰ ) | s ∈ sat(Xϕ _i ) ⇔ s ⁰ ∈ sat(ϕ _i )

Building the tableau T ψ for ψ: initial states and transition relation

Set of states in S _{T ψ} satisfying ϕ _i : sat(ϕ _i ) sat(ϕ ₁ ) := {s | ϕ ₁ ∈ s}, ϕ ₁ ∈ el(ψ) sat(¬ϕ 1 ) := S T

/sat(ϕ 1 )

sat(ϕ 1 ∧ ϕ ₂ ) := sat(ϕ 1 ) ∩ sat(ϕ 2 )

sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∪ (sat(ϕ 1 ) ∩ sat(X(ϕ 1 Uϕ 2 )))

Intuition: sat() establishes in which states subformulas are true The set of initial states I _{T ψ} is defined as

I _{T ψ} = sat(ψ)

The transition relation R _{T ψ} is defined as R _{T ψ} (s, s ⁰ ) = \

Xϕ _i ∈el(ψ)

(s, s ⁰ ) | s ∈ sat(Xϕ _i ) ⇔ s ⁰ ∈ sat(ϕ _i )

Building the tableau T ψ for ψ: initial states and transition relation

Set of states in S _{T ψ} satisfying ϕ _i : sat(ϕ _i ) sat(ϕ ₁ ) := {s | ϕ ₁ ∈ s}, ϕ ₁ ∈ el(ψ) sat(¬ϕ 1 ) := S T

/sat(ϕ 1 )

sat(ϕ 1 ∧ ϕ ₂ ) := sat(ϕ 1 ) ∩ sat(ϕ 2 )

sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∪ (sat(ϕ 1 ) ∩ sat(X(ϕ 1 Uϕ 2 )))

Intuition: sat() establishes in which states subformulas are true The set of initial states I _{T ψ} is defined as

I _{T ψ} = sat(ψ)

The transition relation R _{T ψ} is defined as R _{T ψ} (s, s ⁰ ) = \

Xϕ _i ∈el(ψ)

(s, s ⁰ ) | s ∈ sat(Xϕ _i ) ⇔ s ⁰ ∈ sat(ϕ _i )

Building the tableau T ψ for ψ: initial states and transition relation

Set of states in S _{T ψ} satisfying ϕ _i : sat(ϕ _i ) sat(ϕ ₁ ) := {s | ϕ ₁ ∈ s}, ϕ ₁ ∈ el(ψ) sat(¬ϕ 1 ) := S T

/sat(ϕ 1 )

sat(ϕ 1 ∧ ϕ ₂ ) := sat(ϕ 1 ) ∩ sat(ϕ 2 )

sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∪ (sat(ϕ 1 ) ∩ sat(X(ϕ 1 Uϕ 2 )))

Intuition: sat() establishes in which states subformulas are true The set of initial states I _{T ψ} is defined as

I _{T ψ} = sat(ψ)

The transition relation R _{T ψ} is defined as R _{T ψ} (s, s ⁰ ) = \

Xϕ _i ∈el(ψ)

(s, s ⁰ ) | s ∈ sat(Xϕ _i ) ⇔ s ⁰ ∈ sat(ϕ _i )

Example: ψ := pUq [cont.]

Xψ Xψ Xψ

−Xψ Xψ −Xψ

−Xψ −Xψ

3

4

5 6

7 8

2 1 p q

ψ

−p p −q

−p q −p −q p q

p −q −p −q

ψ

ψ −ψ ψ

−ψ

−ψ

q

ψ

Problems with U-subformulas

R _{T ψ} does not guarantee that the U-subformulas are fulfilled Example: state 3 {p, ¬q, X(pUq)}:

although state 3 belongs to

sat(pUq) := sat(q) ∪ (sat(p) ∩ sat(X(pUq))),

the path which loops forever in state 3 does not satisfy pUq, as q

never holds in that path.

Problems with U-subformulas

R _{T ψ} does not guarantee that the U-subformulas are fulfilled Example: state 3 {p, ¬q, X(pUq)}:

although state 3 belongs to

sat(pUq) := sat(q) ∪ (sat(p) ∩ sat(X(pUq))),

the path which loops forever in state 3 does not satisfy pUq, as q

never holds in that path.

Problems with U-subformulas

R _{T ψ} does not guarantee that the U-subformulas are fulfilled Example: state 3 {p, ¬q, X(pUq)}:

although state 3 belongs to

sat(pUq) := sat(q) ∪ (sat(p) ∩ sat(X(pUq))),

the path which loops forever in state 3 does not satisfy pUq, as q

never holds in that path.

Tableaux rules: a quote

“After all... tomorrow is another day."

[Scarlett O’Hara, “Gone with the Wind”]

Fairness conditions for every U-subformula

it must never happen that we get into a state s ⁰ from which we can enter a path π ⁰ in which ϕ ₁ Uϕ ₂ holds forever and ϕ ₂ never holds.

In CTL*: ¬EFEG((ϕ ₁ Uϕ ₂ ) ∧ ¬ϕ ₂ ) (“bad loop”)

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2 . . . .

−ϕ2 −ϕ2

=⇒ For every [positive] U-subformula ϕ ₁ Uϕ ₂ of ψ, we must add a fairness CTL* condition AGAF(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ 2 )

(in LTL: GF(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ))

If no [positive] U-subformulas, then add one fairness condition AGAF>.

=⇒ We restrict the admissible paths of T _ψ to those which verify the fairness condition: T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i

F _{T ψ} := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Fairness conditions for every U-subformula

it must never happen that we get into a state s ⁰ from which we can enter a path π ⁰ in which ϕ ₁ Uϕ ₂ holds forever and ϕ ₂ never holds.

In CTL*: ¬EFEG((ϕ ₁ Uϕ ₂ ) ∧ ¬ϕ ₂ ) (“bad loop”)

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2 . . . .

−ϕ2 −ϕ2

=⇒ For every [positive] U-subformula ϕ ₁ Uϕ ₂ of ψ, we must add a fairness CTL* condition AGAF(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ 2 )

(in LTL: GF(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ))

If no [positive] U-subformulas, then add one fairness condition AGAF>.

=⇒ We restrict the admissible paths of T _ψ to those which verify the fairness condition: T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i

F _{T ψ} := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Fairness conditions for every U-subformula

it must never happen that we get into a state s ⁰ from which we can enter a path π ⁰ in which ϕ ₁ Uϕ ₂ holds forever and ϕ ₂ never holds.

In CTL*: ¬EFEG((ϕ ₁ Uϕ ₂ ) ∧ ¬ϕ ₂ ) (“bad loop”)

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2 . . . .

−ϕ2 −ϕ2

=⇒ For every [positive] U-subformula ϕ ₁ Uϕ ₂ of ψ, we must add a fairness CTL* condition AGAF(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ 2 )

(in LTL: GF(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ))

If no [positive] U-subformulas, then add one fairness condition AGAF>.

=⇒ We restrict the admissible paths of T _ψ to those which verify the fairness condition: T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i

F _{T ψ} := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Fairness conditions for every U-subformula

it must never happen that we get into a state s ⁰ from which we can enter a path π ⁰ in which ϕ ₁ Uϕ ₂ holds forever and ϕ ₂ never holds.

In CTL*: ¬EFEG((ϕ ₁ Uϕ ₂ ) ∧ ¬ϕ ₂ ) (“bad loop”)

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2 . . . .

−ϕ2 −ϕ2

=⇒ For every [positive] U-subformula ϕ ₁ Uϕ ₂ of ψ, we must add a fairness CTL* condition AGAF(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ 2 )

(in LTL: GF(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ))

If no [positive] U-subformulas, then add one fairness condition AGAF>.

=⇒ We restrict the admissible paths of T _ψ to those which verify the fairness condition: T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i

F _{T ψ} := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Example: ψ := pUq [cont.]

Xψ Xψ Xψ

−Xψ Xψ −Xψ

−Xψ −Xψ

3

4

5 6

7 8

2 1 p q

ψ

−p p −q

−p q −p −q p q

p −q −p −q

ψ

ψ −ψ ψ

−ψ

−ψ

q

ψ

Symbolic representation of T ψ

State variables: one Boolean variable for each formula in el(ψ) EX: p, q and x and primed versions p ⁰ , q ⁰ and x ⁰

[ x is a Boolean label for X(pUq) ] sat(ϕ _i ):

sat(p) := p, s.t. p Boolean state variable sat(¬ϕ ₁ ) := ¬sat(ϕ ₁ )

sat(ϕ ₁ ∧ ϕ ₂ ) := sat(ϕ ₁ ) ∧ sat(ϕ ₂ )

sat(Xϕ i ) := x _[Xϕ

] , s.t. x _[Xϕ

] Boolean state variable sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∨ (sat(ϕ 1 ) ∧ sat(X(ϕ 1 Uϕ 2 )))

=⇒ sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∨ (sat(ϕ 1 ) ∧ x _[Xϕ

_Uϕ

] )

...

Symbolic representation of T ψ

State variables: one Boolean variable for each formula in el(ψ) EX: p, q and x and primed versions p ⁰ , q ⁰ and x ⁰

[ x is a Boolean label for X(pUq) ] sat(ϕ _i ):

sat(p) := p, s.t. p Boolean state variable sat(¬ϕ ₁ ) := ¬sat(ϕ ₁ )

sat(ϕ ₁ ∧ ϕ ₂ ) := sat(ϕ ₁ ) ∧ sat(ϕ ₂ )

sat(Xϕ i ) := x _[Xϕ

] , s.t. x _[Xϕ

] Boolean state variable sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∨ (sat(ϕ 1 ) ∧ sat(X(ϕ 1 Uϕ 2 )))

=⇒ sat(ϕ 1 Uϕ 2 ) := sat(ϕ 2 ) ∨ (sat(ϕ 1 ) ∧ x _[Xϕ

_Uϕ

] )

...

Symbolic representation of T ψ [cont.]

...

Initial states: I _{T ψ} = sat(ψ) EX: I(p, q, x ) = q ∨ (p ∧ x ) Transition Relation:

R _{T ψ} (s, s ⁰ ) = T

Xϕ i ∈el(ψ) {(s, s ⁰ ) | s ∈ sat(Xϕ _i ) ⇔ s ⁰ ∈ sat(ϕ _i )}

R _T

= V

Xϕ

∈el(ψ) (sat(Xϕ _i ) ↔ sat ⁰ (ϕ _i )) where sat ⁰ (ϕ _i ) is sat(ϕ _i ) on primed variables EX: R _T

(p, q, x , p ⁰ , q ⁰ , x ⁰ ) = x ↔ (q ⁰ ∨ (p ⁰ ∧ x ⁰ )) Fairness Conditions:

F _{T ψ} := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ 2 )) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

EX: F _T

(p, q, x ) = ¬(q ∨ (p ∧ x )) ∨ q = ... = ¬p ∨ ¬x ∨ q

Symbolic representation of T ψ [cont.]

...

Initial states: I _{T ψ} = sat(ψ) EX: I(p, q, x ) = q ∨ (p ∧ x ) Transition Relation:

R _{T ψ} (s, s ⁰ ) = T

Xϕ i ∈el(ψ) {(s, s ⁰ ) | s ∈ sat(Xϕ _i ) ⇔ s ⁰ ∈ sat(ϕ _i )}

R _T

= V

Xϕ

∈el(ψ) (sat(Xϕ _i ) ↔ sat ⁰ (ϕ _i )) where sat ⁰ (ϕ _i ) is sat(ϕ _i ) on primed variables EX: R _T

(p, q, x , p ⁰ , q ⁰ , x ⁰ ) = x ↔ (q ⁰ ∨ (p ⁰ ∧ x ⁰ )) Fairness Conditions:

F _{T ψ} := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ 2 )) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

EX: F _T

(p, q, x ) = ¬(q ∨ (p ∧ x )) ∨ q = ... = ¬p ∨ ¬x ∨ q

Symbolic representation of T ψ [cont.]

...

Initial states: I _{T ψ} = sat(ψ) EX: I(p, q, x ) = q ∨ (p ∧ x ) Transition Relation:

R _{T ψ} (s, s ⁰ ) = T

Xϕ i ∈el(ψ) {(s, s ⁰ ) | s ∈ sat(Xϕ _i ) ⇔ s ⁰ ∈ sat(ϕ _i )}

R _T

= V

Xϕ

∈el(ψ) (sat(Xϕ _i ) ↔ sat ⁰ (ϕ _i )) where sat ⁰ (ϕ _i ) is sat(ϕ _i ) on primed variables EX: R _T

(p, q, x , p ⁰ , q ⁰ , x ⁰ ) = x ↔ (q ⁰ ∨ (p ⁰ ∧ x ⁰ )) Fairness Conditions:

F _{T ψ} := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ 2 )) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

EX: F _T

(p, q, x ) = ¬(q ∨ (p ∧ x )) ∨ q = ... = ¬p ∨ ¬x ∨ q

Symbolic representation of T ψ : examples

I _{T ψ} (p, q, x ) = q ∨ (p ∧ x ) 1 : {p, q, x } |= I _{T ψ} 3 : {p, ¬q, x } |= I _{T ψ} 6 5 : {¬p, ¬q, x} 6|= I _{T ψ} R _{T ψ} (p, q, x , p ⁰ , q ⁰ , x ⁰ ) = x ↔ (q ⁰ ∨ (p ⁰ ∧ x ⁰ ))

1 ⇒ 1 : {p, q, x , p ⁰ , q ⁰ , x ⁰ } |= R _{T ψ} 6 ⇒ 7 : {p, q, ¬x , p ⁰ , ¬q ⁰ , ¬x ⁰ } |= R _{T ψ} 6 6⇒ 1 : {p, q, ¬x , p ⁰ , q ⁰ , x ⁰ } 6|= R _{T ψ} F _{T ψ} (p, q, x ) = ¬p ∨ ¬x ∨ q

1 : {p, q, x } |= F _{T ψ} 5 : {¬p, ¬q, x } |= F _{T ψ} 6 3 : {p, ¬q, x} 6|= F T _ψ

Xψ Xψ Xψ

−Xψ Xψ −Xψ

−Xψ −Xψ

3

4

5 6

7 8

2 1 pq

ψ

−p p−q

−p q −p−q p q

p −q −p −q

ψ

ψ −ψ ψ

−ψ

−ψ

q ψ

Symbolic representation of T ψ : examples

I _{T ψ} (p, q, x ) = q ∨ (p ∧ x ) 1 : {p, q, x } |= I _{T ψ} 3 : {p, ¬q, x } |= I _{T ψ} 6 5 : {¬p, ¬q, x} 6|= I _{T ψ} R _{T ψ} (p, q, x , p ⁰ , q ⁰ , x ⁰ ) = x ↔ (q ⁰ ∨ (p ⁰ ∧ x ⁰ ))

1 ⇒ 1 : {p, q, x , p ⁰ , q ⁰ , x ⁰ } |= R _{T ψ} 6 ⇒ 7 : {p, q, ¬x , p ⁰ , ¬q ⁰ , ¬x ⁰ } |= R _{T ψ} 6 6⇒ 1 : {p, q, ¬x , p ⁰ , q ⁰ , x ⁰ } 6|= R _{T ψ} F _{T ψ} (p, q, x ) = ¬p ∨ ¬x ∨ q

1 : {p, q, x } |= F _{T ψ} 5 : {¬p, ¬q, x } |= F _{T ψ} 6 3 : {p, ¬q, x} 6|= F T _ψ

Xψ Xψ Xψ

−Xψ Xψ −Xψ

−Xψ −Xψ

3

4

5 6

7 8

2 1 pq

ψ

−p p−q

−p q −p−q p q

p −q −p −q

ψ

ψ −ψ ψ

−ψ

−ψ

q ψ

Symbolic representation of T ψ : examples

I _{T ψ} (p, q, x ) = q ∨ (p ∧ x ) 1 : {p, q, x } |= I _{T ψ} 3 : {p, ¬q, x } |= I _{T ψ} 6 5 : {¬p, ¬q, x} 6|= I _{T ψ} R _{T ψ} (p, q, x , p ⁰ , q ⁰ , x ⁰ ) = x ↔ (q ⁰ ∨ (p ⁰ ∧ x ⁰ ))

1 ⇒ 1 : {p, q, x , p ⁰ , q ⁰ , x ⁰ } |= R _{T ψ} 6 ⇒ 7 : {p, q, ¬x , p ⁰ , ¬q ⁰ , ¬x ⁰ } |= R _{T ψ} 6 6⇒ 1 : {p, q, ¬x , p ⁰ , q ⁰ , x ⁰ } 6|= R _{T ψ} F _{T ψ} (p, q, x ) = ¬p ∨ ¬x ∨ q

1 : {p, q, x } |= F _{T ψ} 5 : {¬p, ¬q, x } |= F _{T ψ} 6 3 : {p, ¬q, x} 6|= F T _ψ

Xψ Xψ Xψ

−Xψ Xψ −Xψ

−Xψ −Xψ

3

4

5 6

7 8

2 1 pq

ψ

−p p−q

−p q −p−q p q

p −q −p −q

ψ

ψ −ψ ψ

−ψ

−ψ

q ψ

Symbolic representation of T ψ : examples

I _{T ψ} (p, q, x ) = q ∨ (p ∧ x ) 1 : {p, q, x } |= I _{T ψ} 3 : {p, ¬q, x } |= I _{T ψ} 6 5 : {¬p, ¬q, x} 6|= I _{T ψ} R _{T ψ} (p, q, x , p ⁰ , q ⁰ , x ⁰ ) = x ↔ (q ⁰ ∨ (p ⁰ ∧ x ⁰ ))

1 ⇒ 1 : {p, q, x , p ⁰ , q ⁰ , x ⁰ } |= R _{T ψ} 6 ⇒ 7 : {p, q, ¬x , p ⁰ , ¬q ⁰ , ¬x ⁰ } |= R _{T ψ} 6 6⇒ 1 : {p, q, ¬x , p ⁰ , q ⁰ , x ⁰ } 6|= R _{T ψ} F _{T ψ} (p, q, x ) = ¬p ∨ ¬x ∨ q

1 : {p, q, x } |= F _{T ψ} 5 : {¬p, ¬q, x } |= F _{T ψ} 6 3 : {p, ¬q, x} 6|= F T _ψ

Xψ Xψ Xψ

−Xψ Xψ −Xψ

−Xψ −Xψ

3

4

5 6

7 8

2 1 pq

ψ

−p p−q

−p q −p−q p q

p −q −p −q

ψ

ψ −ψ ψ

−ψ

−ψ

q ψ

Outline

1 The problem

2 The general algorithm Compute the tableau T _ψ Compute the product M × T _ψ Check the emptiness of L(M × T _ψ )

3 An example

4 Exercises

Computing the product P := T ψ × M

Given M := hS _M , I _M , R _M , L _M i and T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i, we compute the product P := T _ψ × M = hS, I, R, L, F i as follows:

S := {(s, s ⁰ ) | s ∈ S T

, s ⁰ ∈ S _M and L M (s ⁰ )| _ψ = L T

(s)}

I := {(s, s ⁰ ) | s ∈ I T

, s ⁰ ∈ I _M and L M (s ⁰ )| _ψ = L T

(s)}

Given (s, s ⁰ ), (t, t ⁰ ) ∈ S, ((s, s ⁰ ), (t, t ⁰ )) ∈ R iff (s, t) ∈ R T

and (s ⁰ , t ⁰ ) ∈ R M

L((s, s ⁰ )) = L T

(s) ∪ L M (s ⁰ ) Extension of sat() and F _{T ψ} to P:

(s, s ⁰ ) ∈ sat(ψ) ⇐⇒ s ∈ sat(ψ)

F := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Computing the product P := T ψ × M

Given M := hS _M , I _M , R _M , L _M i and T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i, we compute the product P := T _ψ × M = hS, I, R, L, F i as follows:

S := {(s, s ⁰ ) | s ∈ S T

, s ⁰ ∈ S _M and L M (s ⁰ )| _ψ = L T

(s)}

I := {(s, s ⁰ ) | s ∈ I T

, s ⁰ ∈ I _M and L M (s ⁰ )| _ψ = L T

(s)}

Given (s, s ⁰ ), (t, t ⁰ ) ∈ S, ((s, s ⁰ ), (t, t ⁰ )) ∈ R iff (s, t) ∈ R T

and (s ⁰ , t ⁰ ) ∈ R M

L((s, s ⁰ )) = L T

(s) ∪ L M (s ⁰ ) Extension of sat() and F _{T ψ} to P:

(s, s ⁰ ) ∈ sat(ψ) ⇐⇒ s ∈ sat(ψ)

F := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Computing the product P := T ψ × M

Given M := hS _M , I _M , R _M , L _M i and T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i, we compute the product P := T _ψ × M = hS, I, R, L, F i as follows:

S := {(s, s ⁰ ) | s ∈ S T

, s ⁰ ∈ S _M and L M (s ⁰ )| _ψ = L T

(s)}

I := {(s, s ⁰ ) | s ∈ I T

, s ⁰ ∈ I _M and L M (s ⁰ )| _ψ = L T

(s)}

Given (s, s ⁰ ), (t, t ⁰ ) ∈ S, ((s, s ⁰ ), (t, t ⁰ )) ∈ R iff (s, t) ∈ R T

and (s ⁰ , t ⁰ ) ∈ R M

L((s, s ⁰ )) = L T

(s) ∪ L M (s ⁰ ) Extension of sat() and F _{T ψ} to P:

(s, s ⁰ ) ∈ sat(ψ) ⇐⇒ s ∈ sat(ψ)

F := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Computing the product P := T ψ × M

Given M := hS _M , I _M , R _M , L _M i and T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i, we compute the product P := T _ψ × M = hS, I, R, L, F i as follows:

S := {(s, s ⁰ ) | s ∈ S T

, s ⁰ ∈ S _M and L M (s ⁰ )| _ψ = L T

(s)}

I := {(s, s ⁰ ) | s ∈ I T

, s ⁰ ∈ I _M and L M (s ⁰ )| _ψ = L T

(s)}

Given (s, s ⁰ ), (t, t ⁰ ) ∈ S, ((s, s ⁰ ), (t, t ⁰ )) ∈ R iff (s, t) ∈ R T

and (s ⁰ , t ⁰ ) ∈ R M

L((s, s ⁰ )) = L T

(s) ∪ L M (s ⁰ ) Extension of sat() and F _{T ψ} to P:

(s, s ⁰ ) ∈ sat(ψ) ⇐⇒ s ∈ sat(ψ)

F := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Computing the product P := T ψ × M

Given M := hS _M , I _M , R _M , L _M i and T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i, we compute the product P := T _ψ × M = hS, I, R, L, F i as follows:

S := {(s, s ⁰ ) | s ∈ S T

, s ⁰ ∈ S _M and L M (s ⁰ )| _ψ = L T

(s)}

I := {(s, s ⁰ ) | s ∈ I T

, s ⁰ ∈ I _M and L M (s ⁰ )| _ψ = L T

(s)}

Given (s, s ⁰ ), (t, t ⁰ ) ∈ S, ((s, s ⁰ ), (t, t ⁰ )) ∈ R iff (s, t) ∈ R T

and (s ⁰ , t ⁰ ) ∈ R M

L((s, s ⁰ )) = L T

(s) ∪ L M (s ⁰ ) Extension of sat() and F _{T ψ} to P:

(s, s ⁰ ) ∈ sat(ψ) ⇐⇒ s ∈ sat(ψ)

F := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Computing the product P := T ψ × M

Given M := hS _M , I _M , R _M , L _M i and T _ψ := hS _{T ψ} , I _{T ψ} , R _{T ψ} , L _{T ψ} , F _{T ψ} i, we compute the product P := T _ψ × M = hS, I, R, L, F i as follows:

S := {(s, s ⁰ ) | s ∈ S T

, s ⁰ ∈ S _M and L M (s ⁰ )| _ψ = L T

(s)}

I := {(s, s ⁰ ) | s ∈ I T

, s ⁰ ∈ I _M and L M (s ⁰ )| _ψ = L T

(s)}

Given (s, s ⁰ ), (t, t ⁰ ) ∈ S, ((s, s ⁰ ), (t, t ⁰ )) ∈ R iff (s, t) ∈ R T

and (s ⁰ , t ⁰ ) ∈ R M

L((s, s ⁰ )) = L T

(s) ∪ L M (s ⁰ ) Extension of sat() and F _{T ψ} to P:

(s, s ⁰ ) ∈ sat(ψ) ⇐⇒ s ∈ sat(ψ)

F := {sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ ) s.t. (ϕ ₁ Uϕ ₂ ) occurs [positively ]in ψ}

Computing the product P := T ψ × M symbolically

Let V , W be the array of Boolean state variables of T _ψ and M respectively:

Initial states: I(V ∪ W ) = I _{T ψ} (V ) ∧ I _M (W )

Transition Relation: R(V ∪ W , V ⁰ ∪ W ⁰ ) = R _{T ψ} (V , V ⁰ ) ∧ R _M (W , W ⁰ ) Fairness conditions:

{F ₁ (V ∪ W ), ..., F _k (V ∪ W )} = {F _{T ψ 1} (V ), ..., F _{T ψ k} (V )}

Computing the product P := T ψ × M symbolically

Let V , W be the array of Boolean state variables of T _ψ and M respectively:

Initial states: I(V ∪ W ) = I _{T ψ} (V ) ∧ I _M (W )

Transition Relation: R(V ∪ W , V ⁰ ∪ W ⁰ ) = R _{T ψ} (V , V ⁰ ) ∧ R _M (W , W ⁰ ) Fairness conditions:

{F ₁ (V ∪ W ), ..., F _k (V ∪ W )} = {F _{T ψ 1} (V ), ..., F _{T ψ k} (V )}

Computing the product P := T ψ × M symbolically

Let V , W be the array of Boolean state variables of T _ψ and M respectively:

Initial states: I(V ∪ W ) = I _{T ψ} (V ) ∧ I _M (W )

Transition Relation: R(V ∪ W , V ⁰ ∪ W ⁰ ) = R _{T ψ} (V , V ⁰ ) ∧ R _M (W , W ⁰ ) Fairness conditions:

{F ₁ (V ∪ W ), ..., F _k (V ∪ W )} = {F _{T ψ 1} (V ), ..., F _{T ψ k} (V )}

Computing the product P := T ψ × M symbolically

Let V , W be the array of Boolean state variables of T _ψ and M respectively:

Initial states: I(V ∪ W ) = I _{T ψ} (V ) ∧ I _M (W )

Transition Relation: R(V ∪ W , V ⁰ ∪ W ⁰ ) = R _{T ψ} (V , V ⁰ ) ∧ R _M (W , W ⁰ ) Fairness conditions:

{F ₁ (V ∪ W ), ..., F _k (V ∪ W )} = {F _{T ψ 1} (V ), ..., F _{T ψ k} (V )}

Outline

1 The problem

2 The general algorithm Compute the tableau T _ψ Compute the product M × T _ψ Check the emptiness of L(M × T _ψ )

3 An example

4 Exercises

Main theorem [Clarke, Grumberg & Hamaguchi; 94]

Theorem

THEOREM: M.s ⁰ |= Eψ iff there is a state s in T _ψ s.t. (s, s ⁰ ) ∈ sat(ψ) and T _ψ × M, (s, s ⁰ ) |= EGtrue under the fairness conditions:

{sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs in ψ}.

=⇒ M |= Eψ iff T _ψ × M |= E _f Gtrue

=⇒ M |= ¬ψ iff T _ψ × M 6|= E _f Gtrue LTL M.C. reduced to Fair CTL M.C.!!!

Symbolic OBDD-based techniques apply.

Note

The transition relation R of T _ψ × M may not be total.

=⇒ Check_FairEG does not need to consider states without

successors, restricting R to the remaining states.

Main theorem [Clarke, Grumberg & Hamaguchi; 94]

Theorem

THEOREM: M.s ⁰ |= Eψ iff there is a state s in T _ψ s.t. (s, s ⁰ ) ∈ sat(ψ) and T _ψ × M, (s, s ⁰ ) |= EGtrue under the fairness conditions:

{sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs in ψ}.

=⇒ M |= Eψ iff T _ψ × M |= E _f Gtrue

=⇒ M |= ¬ψ iff T _ψ × M 6|= E _f Gtrue LTL M.C. reduced to Fair CTL M.C.!!!

Symbolic OBDD-based techniques apply.

Note

The transition relation R of T _ψ × M may not be total.

=⇒ Check_FairEG does not need to consider states without

successors, restricting R to the remaining states.

Main theorem [Clarke, Grumberg & Hamaguchi; 94]

Theorem

THEOREM: M.s ⁰ |= Eψ iff there is a state s in T _ψ s.t. (s, s ⁰ ) ∈ sat(ψ) and T _ψ × M, (s, s ⁰ ) |= EGtrue under the fairness conditions:

{sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs in ψ}.

=⇒ M |= Eψ iff T _ψ × M |= E _f Gtrue

=⇒ M |= ¬ψ iff T _ψ × M 6|= E _f Gtrue LTL M.C. reduced to Fair CTL M.C.!!!

Symbolic OBDD-based techniques apply.

Note

The transition relation R of T _ψ × M may not be total.

=⇒ Check_FairEG does not need to consider states without

successors, restricting R to the remaining states.

Main theorem [Clarke, Grumberg & Hamaguchi; 94]

Theorem

THEOREM: M.s ⁰ |= Eψ iff there is a state s in T _ψ s.t. (s, s ⁰ ) ∈ sat(ψ) and T _ψ × M, (s, s ⁰ ) |= EGtrue under the fairness conditions:

{sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs in ψ}.

=⇒ M |= Eψ iff T _ψ × M |= E _f Gtrue

=⇒ M |= ¬ψ iff T _ψ × M 6|= E _f Gtrue LTL M.C. reduced to Fair CTL M.C.!!!

Symbolic OBDD-based techniques apply.

Note

The transition relation R of T _ψ × M may not be total.

=⇒ Check_FairEG does not need to consider states without

successors, restricting R to the remaining states.

Main theorem [Clarke, Grumberg & Hamaguchi; 94]

Theorem

THEOREM: M.s ⁰ |= Eψ iff there is a state s in T _ψ s.t. (s, s ⁰ ) ∈ sat(ψ) and T _ψ × M, (s, s ⁰ ) |= EGtrue under the fairness conditions:

{sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs in ψ}.

=⇒ M |= Eψ iff T _ψ × M |= E _f Gtrue

=⇒ M |= ¬ψ iff T _ψ × M 6|= E _f Gtrue LTL M.C. reduced to Fair CTL M.C.!!!

Symbolic OBDD-based techniques apply.

Note

The transition relation R of T _ψ × M may not be total.

=⇒ Check_FairEG does not need to consider states without

successors, restricting R to the remaining states.

Main theorem [Clarke, Grumberg & Hamaguchi; 94]

Theorem

THEOREM: M.s ⁰ |= Eψ iff there is a state s in T _ψ s.t. (s, s ⁰ ) ∈ sat(ψ) and T _ψ × M, (s, s ⁰ ) |= EGtrue under the fairness conditions:

{sat(¬(ϕ ₁ Uϕ ₂ ) ∨ ϕ ₂ )) s.t. (ϕ ₁ Uϕ ₂ ) occurs in ψ}.

=⇒ M |= Eψ iff T _ψ × M |= E _f Gtrue

=⇒ M |= ¬ψ iff T _ψ × M 6|= E _f Gtrue LTL M.C. reduced to Fair CTL M.C.!!!

Symbolic OBDD-based techniques apply.

Note

The transition relation R of T _ψ × M may not be total.

=⇒ Check_FairEG does not need to consider states without

successors, restricting R to the remaining states.

Outline

1 The problem

2 The general algorithm Compute the tableau T _ψ Compute the product M × T _ψ Check the emptiness of L(M × T _ψ )

3 An example

4 Exercises

A microwave oven

4 variables: start, close, heat, error

Actions (implicit): start_oven,open_door, close_door, reset, warmup, start_cooking, cook, done

Error situation: if oven is started while the door is open

Represented as a Kripke structure (and hence as a OBDD’s)

A microwave oven [cont.]

1

2 3 4

5 6 7

−start

−close

−heat

−error

−close

−heat

−start

−heat

−error

−start

−error

−error

−heat

−error

−heat start

error

close close

heat

start close error

start close

start close heat start_owen open_door

close_door

open_door

open_door

close_door reset start_owen start_cooking

warmup done

cook

A microwave oven: symbolic representation

Initial states: I _M (s, c, h, e) = ¬s ∧ ¬h ∧ ¬e

Transition relation: R _M (s, c, h, e, s ⁰ , c ⁰ , h ⁰ , e ⁰ ) = [a simplification of]

( ¬s∧¬c∧¬h∧¬e∧¬s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) ∨ (close_door , no error ) ( s∧¬c∧¬h∧ e∧ s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧ e ⁰ ) ∨ (close_door , error ) ( ¬s∧ c ∧¬e∧¬s ⁰ ∧¬c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) ∨ (open_door , no error ) ( s∧ c∧¬h∧ e∧ s ⁰ ∧¬c ⁰ ∧¬h ⁰ ∧ e ⁰ ) ∨ (open_door , error ) ( ¬s∧ c∧¬h∧¬e∧ s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) ∨ (start_oven, no error ) ( ¬s∧¬c∧¬h∧¬e∧ s ⁰ ∧¬c ⁰ ∧¬h ⁰ ∧ e ⁰ ) ∨ (start_oven, error ) ( s∧ c∧¬h∧ e∧¬s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) ∨ (reset)

( s∧ c∧¬h∧¬e∧ s ⁰ ∧ c ⁰ ∧ h ⁰ ∧¬e ⁰ ) ∨ (warmup) ( s∧ c∧ h∧¬e∧¬s ⁰ ∧ c ⁰ ∧ h ⁰ ∧¬e ⁰ ) ∨ (start_cooking) ( ¬s∧ c∧ h∧¬e∧¬s ⁰ ∧ c ⁰ ∧ h ⁰ ∧¬e ⁰ ) ∨ (cook )

( ¬s∧ c∧ h∧¬e∧¬s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) (done)

Note: the third row represents two transitions: 3 → 1 and 4 → 1.

A microwave oven: symbolic representation

Initial states: I _M (s, c, h, e) = ¬s ∧ ¬h ∧ ¬e

Transition relation: R _M (s, c, h, e, s ⁰ , c ⁰ , h ⁰ , e ⁰ ) = [a simplification of]

( ¬s∧¬c∧¬h∧¬e∧¬s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) ∨ (close_door , no error ) ( s∧¬c∧¬h∧ e∧ s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧ e ⁰ ) ∨ (close_door , error ) ( ¬s∧ c ∧¬e∧¬s ⁰ ∧¬c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) ∨ (open_door , no error ) ( s∧ c∧¬h∧ e∧ s ⁰ ∧¬c ⁰ ∧¬h ⁰ ∧ e ⁰ ) ∨ (open_door , error ) ( ¬s∧ c∧¬h∧¬e∧ s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) ∨ (start_oven, no error ) ( ¬s∧¬c∧¬h∧¬e∧ s ⁰ ∧¬c ⁰ ∧¬h ⁰ ∧ e ⁰ ) ∨ (start_oven, error ) ( s∧ c∧¬h∧ e∧¬s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) ∨ (reset)

( s∧ c∧¬h∧¬e∧ s ⁰ ∧ c ⁰ ∧ h ⁰ ∧¬e ⁰ ) ∨ (warmup) ( s∧ c∧ h∧¬e∧¬s ⁰ ∧ c ⁰ ∧ h ⁰ ∧¬e ⁰ ) ∨ (start_cooking) ( ¬s∧ c∧ h∧¬e∧¬s ⁰ ∧ c ⁰ ∧ h ⁰ ∧¬e ⁰ ) ∨ (cook )

( ¬s∧ c∧ h∧¬e∧¬s ⁰ ∧ c ⁰ ∧¬h ⁰ ∧¬e ⁰ ) (done)

Note: the third row represents two transitions: 3 → 1 and 4 → 1.

LTL specification

“necessarily, the oven’s door eventually closes and, till there, the oven does not heat”:

M |= A(¬heat U close), i.e.,

M |= ¬E¬(¬heat U close)

Tableau construction for ψ = ¬(¬heat U close)

ϕ := ¬ψ = (¬heat U close) Tableaux expansion:

ψ = ¬(¬heat U close) = ¬(close ∨ (¬heat ∧ X(¬heat U close))) el(ψ) = el(ϕ) = {heat, close, Xϕ} ({h, c, Xϕ})

States:

1 := {¬h, c, Xϕ}, 2 := {h, c, Xϕ}, 3 := {¬h, ¬c, Xϕ},

4 := {h, c, ¬Xϕ}, 5 := {h, ¬c, Xϕ}, 6 := {¬h, c, ¬Xϕ},

7 := {¬h, ¬c, ¬Xϕ}, 8 := {h, ¬c, ¬Xϕ}

Tableau construction for ψ = ¬(¬heat U close)

ϕ := ¬ψ = (¬heat U close) Tableaux expansion:

ψ = ¬(¬heat U close) = ¬(close ∨ (¬heat ∧ X(¬heat U close))) el(ψ) = el(ϕ) = {heat, close, Xϕ} ({h, c, Xϕ})

States:

1 := {¬h, c, Xϕ}, 2 := {h, c, Xϕ}, 3 := {¬h, ¬c, Xϕ},

4 := {h, c, ¬Xϕ}, 5 := {h, ¬c, Xϕ}, 6 := {¬h, c, ¬Xϕ},

7 := {¬h, ¬c, ¬Xϕ}, 8 := {h, ¬c, ¬Xϕ}

Tableau construction for ψ = ¬(¬heat U close)

ϕ := ¬ψ = (¬heat U close) Tableaux expansion:

ψ = ¬(¬heat U close) = ¬(close ∨ (¬heat ∧ X(¬heat U close))) el(ψ) = el(ϕ) = {heat, close, Xϕ} ({h, c, Xϕ})

States:

1 := {¬h, c, Xϕ}, 2 := {h, c, Xϕ}, 3 := {¬h, ¬c, Xϕ},

4 := {h, c, ¬Xϕ}, 5 := {h, ¬c, Xϕ}, 6 := {¬h, c, ¬Xϕ},

7 := {¬h, ¬c, ¬Xϕ}, 8 := {h, ¬c, ¬Xϕ}

Tableau construction for ψ = ¬(¬heat U close)

ϕ := ¬ψ = (¬heat U close) Tableaux expansion:

ψ = ¬(¬heat U close) = ¬(close ∨ (¬heat ∧ X(¬heat U close))) el(ψ) = el(ϕ) = {heat, close, Xϕ} ({h, c, Xϕ})

States:

1 := {¬h, c, Xϕ}, 2 := {h, c, Xϕ}, 3 := {¬h, ¬c, Xϕ},

4 := {h, c, ¬Xϕ}, 5 := {h, ¬c, Xϕ}, 6 := {¬h, c, ¬Xϕ},

7 := {¬h, ¬c, ¬Xϕ}, 8 := {h, ¬c, ¬Xϕ}

Tableau construction for ψ = ¬(¬heat U close) [cont.]

Xϕ Xϕ Xϕ

−Xϕ −Xϕ

−Xϕ −Xϕ

Xϕ

−h

−h

−h

−h h

h h

h

c c −c

−c

c c

−c −c

2 3 1

4

5 6

7 8

. .

.

.

Tableau construction for ψ = ¬(¬heat U close)

...

States:

1 := {¬h, c, Xϕ}, 2 := {h, c, Xϕ}, 3 := {¬h, ¬c, Xϕ}, 4 := {h, c, ¬Xϕ}, 5 := {h, ¬c, Xϕ}, 6 := {¬h, c, ¬Xϕ}, 7 := {¬h, ¬c, ¬Xϕ}, 8 := {h, ¬c, ¬Xϕ}

sat():

sat(h) = {2, 4, 5, 8} =⇒ sat(¬h) = {1, 3, 6, 7}, sat(c) = {1, 2, 4, 6} =⇒ sat(¬c) = {3, 5, 7, 8}, sat(Xϕ) = {1, 2, 3, 5} =⇒ sat(¬Xϕ) = {4, 6, 7, 8},

sat(ϕ) = sat(c) ∪ (sat(¬h) ∩ sat(X(¬h U c))) = {1, 2, 3, 4, 6}

=⇒ sat(ψ) = sat(¬ϕ) = {5, 7, 8}

Tableau construction for ψ = ¬(¬heat U close)

...

States:

1 := {¬h, c, Xϕ}, 2 := {h, c, Xϕ}, 3 := {¬h, ¬c, Xϕ}, 4 := {h, c, ¬Xϕ}, 5 := {h, ¬c, Xϕ}, 6 := {¬h, c, ¬Xϕ}, 7 := {¬h, ¬c, ¬Xϕ}, 8 := {h, ¬c, ¬Xϕ}

sat():

sat(h) = {2, 4, 5, 8} =⇒ sat(¬h) = {1, 3, 6, 7}, sat(c) = {1, 2, 4, 6} =⇒ sat(¬c) = {3, 5, 7, 8}, sat(Xϕ) = {1, 2, 3, 5} =⇒ sat(¬Xϕ) = {4, 6, 7, 8},

sat(ϕ) = sat(c) ∪ (sat(¬h) ∩ sat(X(¬h U c))) = {1, 2, 3, 4, 6}

=⇒ sat(ψ) = sat(¬ϕ) = {5, 7, 8}

Tableau construction for ψ = ¬(¬heat U close) [cont.]

Xϕ Xϕ Xϕ

−Xϕ −Xϕ

−Xϕ −Xϕ

Xϕ

−h

−h

−h

−h h

h h

h

c c −c

−c

c c

−c −c

2 3 1

4

5 6

7 8

. .

. .

sat(−h)

sat(−h)

sat(−h)

sat(h)

Tableau construction for ψ = ¬(¬heat U close) [cont.]

Xϕ Xϕ Xϕ

−Xϕ −Xϕ

−Xϕ −Xϕ

Xϕ

−h

−h

−h

−h h

h h

h

c c −c

−c

c c

−c −c

2 3 1

4

5 6

7 8

. .

. .

sat(−h)

sat(−h)

sat(−h)

sat(h)

sat(c)

sat(c)