### 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

^{th}

### 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**

### =⇒ 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**

### =⇒ 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**

### =⇒ 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**

### =⇒ 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**

### =⇒ 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**

### =⇒ 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 ∧ ϕ _{2} ) := el(ϕ 1 ) ∪ el(ϕ 2 ) el(Xϕ 1 ) = {Xϕ 1 } ∪ el(ϕ _{1} )

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

### Intuition: el(ψ) is the set of propositions and **X-formulas occurring** ψ ^{0} , ψ ^{0} 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 ∧ ϕ _{2} ) := el(ϕ 1 ) ∪ el(ϕ 2 ) el(Xϕ 1 ) = {Xϕ 1 } ∪ el(ϕ _{1} )

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

### Intuition: el(ψ) is the set of propositions and **X-formulas occurring** ψ ^{0} , ψ ^{0} 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 ∧ ϕ _{2} ) := el(ϕ 1 ) ∪ el(ϕ 2 ) el(Xϕ 1 ) = {Xϕ 1 } ∪ el(ϕ _{1} )

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

### Intuition: el(ψ) is the set of propositions and **X-formulas occurring** ψ ^{0} , ψ ^{0} 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 ∧ ϕ _{2} ) := el(ϕ 1 ) ∪ el(ϕ 2 ) el(Xϕ 1 ) = {Xϕ 1 } ∪ el(ϕ _{1} )

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

### Intuition: el(ψ) is the set of propositions and **X-formulas occurring** ψ ^{0} , ψ ^{0} 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}, ϕ _{1} ∈ el(ψ) sat(¬ϕ 1 ) := S T

ψ### /sat(ϕ 1 )

### sat(ϕ 1 ∧ ϕ _{2} ) := 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}, ϕ _{1} ∈ el(ψ) sat(¬ϕ 1 ) := S T

ψ### /sat(ϕ 1 )

### sat(ϕ 1 ∧ ϕ _{2} ) := 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(ϕ _{1} ) := {s | ϕ _{1} ∈ s}, ϕ _{1} ∈ el(ψ) sat(¬ϕ 1 ) := S T

ψ### /sat(ϕ 1 )

### sat(ϕ 1 ∧ ϕ _{2} ) := 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 ^{0} ) = \

**Xϕ** _{i} ∈el(ψ)

### (s, s ^{0} ) | s ∈ sat(Xϕ _{i} ) ⇔ s ^{0} ∈ sat(ϕ _{i} )

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

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

ψ### /sat(ϕ 1 )

### sat(ϕ 1 ∧ ϕ _{2} ) := 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 ^{0} ) = \

**Xϕ** _{i} ∈el(ψ)

### (s, s ^{0} ) | s ∈ sat(Xϕ _{i} ) ⇔ s ^{0} ∈ sat(ϕ _{i} )

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

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

ψ### /sat(ϕ 1 )

### sat(ϕ 1 ∧ ϕ _{2} ) := 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 ^{0} ) = \

**Xϕ** _{i} ∈el(ψ)

### (s, s ^{0} ) | s ∈ sat(Xϕ _{i} ) ⇔ s ^{0} ∈ sat(ϕ _{i} )

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

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

ψ### /sat(ϕ 1 )

### sat(ϕ 1 ∧ ϕ _{2} ) := 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 ^{0} ) = \

**Xϕ** _{i} ∈el(ψ)

### (s, s ^{0} ) | s ∈ sat(Xϕ _{i} ) ⇔ s ^{0} ∈ 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 ^{0} from which we can enter a path π ^{0} in which ϕ _{1} **Uϕ** _{2} holds forever and ϕ _{2} never holds.

### In CTL*: **¬EFEG((ϕ** _{1} **Uϕ** _{2} ) ∧ ¬ϕ _{2} ) (“bad loop”)

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2
**. . . .**

−ϕ2 −ϕ2

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

### (in LTL: **GF(¬(ϕ** _{1} **Uϕ** _{2} ) ∨ ϕ _{2} ))

### 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(¬(ϕ _{1} **Uϕ** _{2} ) ∨ ϕ _{2} )) s.t. (ϕ _{1} **Uϕ** _{2} ) occurs [positively ]in ψ}

### Fairness conditions for every **U-subformula**

### it must never happen that we get into a state s ^{0} from which we can enter a path π ^{0} in which ϕ _{1} **Uϕ** _{2} holds forever and ϕ _{2} never holds.

### In CTL*: **¬EFEG((ϕ** _{1} **Uϕ** _{2} ) ∧ ¬ϕ _{2} ) (“bad loop”)

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2
**. . . .**

−ϕ2 −ϕ2

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

### (in LTL: **GF(¬(ϕ** _{1} **Uϕ** _{2} ) ∨ ϕ _{2} ))

### 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(¬(ϕ _{1} **Uϕ** _{2} ) ∨ ϕ _{2} )) s.t. (ϕ _{1} **Uϕ** _{2} ) occurs [positively ]in ψ}

### Fairness conditions for every **U-subformula**

### it must never happen that we get into a state s ^{0} from which we can enter a path π ^{0} in which ϕ _{1} **Uϕ** _{2} holds forever and ϕ _{2} never holds.

### In CTL*: **¬EFEG((ϕ** _{1} **Uϕ** _{2} ) ∧ ¬ϕ _{2} ) (“bad loop”)

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2
**. . . .**

−ϕ2 −ϕ2

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

### (in LTL: **GF(¬(ϕ** _{1} **Uϕ** _{2} ) ∨ ϕ _{2} ))

### 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(¬(ϕ _{1} **Uϕ** _{2} ) ∨ ϕ _{2} )) s.t. (ϕ _{1} **Uϕ** _{2} ) occurs [positively ]in ψ}

### Fairness conditions for every **U-subformula**

### it must never happen that we get into a state s ^{0} from which we can enter a path π ^{0} in which ϕ _{1} **Uϕ** _{2} holds forever and ϕ _{2} never holds.

### In CTL*: **¬EFEG((ϕ** _{1} **Uϕ** _{2} ) ∧ ¬ϕ _{2} ) (“bad loop”)

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2
**. . . .**

−ϕ2 −ϕ2

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

### (in LTL: **GF(¬(ϕ** _{1} **Uϕ** _{2} ) ∨ ϕ _{2} ))

### 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(¬(ϕ _{1} **Uϕ** _{2} ) ∨ ϕ _{2} )) s.t. (ϕ _{1} **Uϕ** _{2} ) 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 ^{0} , q ^{0} and x ^{0}

### [ x is a Boolean label for **X(pUq) ]** sat(ϕ _{i} ):

### sat(p) := p, s.t. p Boolean state variable sat(¬ϕ _{1} ) := ¬sat(ϕ _{1} )

### sat(ϕ _{1} ∧ ϕ _{2} ) := sat(ϕ _{1} ) ∧ sat(ϕ _{2} )

### sat(Xϕ i ) := x _{[Xϕ}

_{i}

### ] , s.t. x _{[Xϕ}

_{i}

### ] 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ϕ}

_{1}

_{Uϕ}

_{Uϕ}

_{2}

### ] )

### ...

### Symbolic representation of T ψ

### State variables: one Boolean variable for each formula in el(ψ) EX: p, q and x and primed versions p ^{0} , q ^{0} and x ^{0}

### [ x is a Boolean label for **X(pUq) ]** sat(ϕ _{i} ):

### sat(p) := p, s.t. p Boolean state variable sat(¬ϕ _{1} ) := ¬sat(ϕ _{1} )

### sat(ϕ _{1} ∧ ϕ _{2} ) := sat(ϕ _{1} ) ∧ sat(ϕ _{2} )

### sat(Xϕ i ) := x _{[Xϕ}

_{i}

### ] , s.t. x _{[Xϕ}

_{i}

### ] 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ϕ}

_{1}

_{Uϕ}

_{Uϕ}

_{2}

### ] )

### ...

### Symbolic representation of T ψ [cont.]

### ...

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

### R _{T} _{ψ} (s, s ^{0} ) = T

**Xϕ** i ∈el(ψ) {(s, s ^{0} ) | s ∈ sat(Xϕ _{i} ) ⇔ s ^{0} ∈ sat(ϕ _{i} )}

### R _{T}

_{ψ}

### = V

**Xϕ**

i### ∈el(ψ) (sat(Xϕ _{i} ) ↔ sat ^{0} (ϕ _{i} )) where sat ^{0} (ϕ _{i} ) is sat(ϕ _{i} ) on primed variables EX: R _{T}

_{ψ}

### (p, q, x , p ^{0} , q ^{0} , x ^{0} ) = x ↔ (q ^{0} ∨ (p ^{0} ∧ x ^{0} )) Fairness Conditions:

### F _{T} _{ψ} := {sat(¬(ϕ _{1} **Uϕ** _{2} ) ∨ ϕ 2 )) s.t. (ϕ _{1} **Uϕ** _{2} ) 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 ^{0} ) = T

**Xϕ** i ∈el(ψ) {(s, s ^{0} ) | s ∈ sat(Xϕ _{i} ) ⇔ s ^{0} ∈ sat(ϕ _{i} )}

### R _{T}

_{ψ}

### = V

**Xϕ**

i### ∈el(ψ) (sat(Xϕ _{i} ) ↔ sat ^{0} (ϕ _{i} )) where sat ^{0} (ϕ _{i} ) is sat(ϕ _{i} ) on primed variables EX: R _{T}

_{ψ}

### (p, q, x , p ^{0} , q ^{0} , x ^{0} ) = x ↔ (q ^{0} ∨ (p ^{0} ∧ x ^{0} )) Fairness Conditions:

### F _{T} _{ψ} := {sat(¬(ϕ _{1} **Uϕ** _{2} ) ∨ ϕ 2 )) s.t. (ϕ _{1} **Uϕ** _{2} ) 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 ^{0} ) = T

**Xϕ** i ∈el(ψ) {(s, s ^{0} ) | s ∈ sat(Xϕ _{i} ) ⇔ s ^{0} ∈ sat(ϕ _{i} )}

### R _{T}

_{ψ}

### = V

**Xϕ**

i### ∈el(ψ) (sat(Xϕ _{i} ) ↔ sat ^{0} (ϕ _{i} )) where sat ^{0} (ϕ _{i} ) is sat(ϕ _{i} ) on primed variables EX: R _{T}

_{ψ}

### (p, q, x , p ^{0} , q ^{0} , x ^{0} ) = x ↔ (q ^{0} ∨ (p ^{0} ∧ x ^{0} )) Fairness Conditions:

### F _{T} _{ψ} := {sat(¬(ϕ _{1} **Uϕ** _{2} ) ∨ ϕ 2 )) s.t. (ϕ _{1} **Uϕ** _{2} ) 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 ^{0} , q ^{0} , x ^{0} ) = x ↔ (q ^{0} ∨ (p ^{0} ∧ x ^{0} ))

### 1 ⇒ 1 : {p, q, x , p ^{0} , q ^{0} , x ^{0} } |= R _{T} _{ψ} 6 ⇒ 7 : {p, q, ¬x , p ^{0} , ¬q ^{0} , ¬x ^{0} } |= R _{T} _{ψ} 6 6⇒ 1 : {p, q, ¬x , p ^{0} , q ^{0} , x ^{0} } 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 ^{0} , q ^{0} , x ^{0} ) = x ↔ (q ^{0} ∨ (p ^{0} ∧ x ^{0} ))

### 1 ⇒ 1 : {p, q, x , p ^{0} , q ^{0} , x ^{0} } |= R _{T} _{ψ} 6 ⇒ 7 : {p, q, ¬x , p ^{0} , ¬q ^{0} , ¬x ^{0} } |= R _{T} _{ψ} 6 6⇒ 1 : {p, q, ¬x , p ^{0} , q ^{0} , x ^{0} } 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 ^{0} , q ^{0} , x ^{0} ) = x ↔ (q ^{0} ∨ (p ^{0} ∧ x ^{0} ))

### 1 ⇒ 1 : {p, q, x , p ^{0} , q ^{0} , x ^{0} } |= R _{T} _{ψ} 6 ⇒ 7 : {p, q, ¬x , p ^{0} , ¬q ^{0} , ¬x ^{0} } |= R _{T} _{ψ} 6 6⇒ 1 : {p, q, ¬x , p ^{0} , q ^{0} , x ^{0} } 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 ^{0} , q ^{0} , x ^{0} ) = x ↔ (q ^{0} ∨ (p ^{0} ∧ x ^{0} ))

### 1 ⇒ 1 : {p, q, x , p ^{0} , q ^{0} , x ^{0} } |= R _{T} _{ψ} 6 ⇒ 7 : {p, q, ¬x , p ^{0} , ¬q ^{0} , ¬x ^{0} } |= R _{T} _{ψ} 6 6⇒ 1 : {p, q, ¬x , p ^{0} , q ^{0} , x ^{0} } 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**
ψ