Formal Methods: Module I: Automated Reasoning Ch. 05: Automata-Theoretic LTL Reasoning

Formal Methods:

Module I: Automated Reasoning

Ch. 05: Automata-Theoretic LTL Reasoning

Roberto Sebastiani and Stefano Tonetta

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

Teaching assistant:Giuseppe Spallitta– giuseppe.spallitta@unitn.it

M.S. in Computer Science, Mathematics, & Artificial Intelligence Systems Academic year 2020-2021

last update: Tuesday 20^thApril, 2021, 12:49

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, C. Tinelli, 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.

1 / 69

Outline

1

Büchi Automata

2

The Automata-Theoretic Approach to LTL Reasoning General Ideas

Language-Emptiness Checking of Büchi Automata From Kripke Models to Büchi Automata

From LTL Formulas to Büchi Automata Complexity

3

Exercises

Outline

1

Büchi Automata

2

The Automata-Theoretic Approach to LTL Reasoning General Ideas

Language-Emptiness Checking of Büchi Automata From Kripke Models to Büchi Automata

From LTL Formulas to Büchi Automata Complexity

3

Exercises

3 / 69

Infinite Word Languages

Modeling infinite computations of reactive systems Given an Alphabet Σ (e.g. Σ

= {a, b})

An ω-word α over Σ is an infinite sequence a

, a

, a

. . ..

Formally, α : N → Σ.

The set of all infinite words is denoted by Σ

.

A ω-language L is collection of ω-words, i.e. L ⊆ Σ

. Example: All words over {a, b} with infinitely many a’s.

Notation:

omega words α, β, γ ∈ Σ

.

omega-languages L, L

⊆ Σ

For u ∈ Σ

, let u

= u.u.u . . .

Omega-Automata

We consider automaton running over infinite words.

Let α = aabbbb . . ..

There are several (infinite) possible runs.

Run ρ

= s

, s

, s

, s

, s

, s

. . . Run ρ

= s

, s

, s

, s

, s

, s

. . .

Acceptance Conditions: Büchi (Muller, Rabin, Street):

Acceptance is based on states occurring infinitely often Notation Let ρ ∈ Q

. Then,

Inf (ρ) = {s ∈ Q | ∃

i ∈ N. ρ(i) = s}.

(The set of states occurring infinitely many times in ρ.)

5 / 69

Büchi Automata

Nondeterministic Büchi Automaton

A Nondeterministic Büchi Automaton (NBA) is (Q, Σ, δ, I, F ) s.t.

Q Finite set of states.

Σis a finite alphabet I ⊆ Q set of initial states.

F ⊆ Q set of accepting states.

δ ⊆Q × Σ × Q transition relation (edges).

A Deterministic Büchi Automaton (DBA) is an NBA s.t. the transition relation is functional: δ : Q × Σ 7−→ Q

Runs and Language of NBAs

A run ρ of A on ω-word α = a

, a

, a

, ... is an infinite sequence ρ = q

, q

, q

, . . . s.t. q

∈ I and q

−→ q

for 0 ≤ i.

The run ρ is accepting if Inf (ρ) ∩ F 6= ∅.

The language accepted by A

L(A) = {α ∈ Σ

| A has an accepting run on α}

Büchi Automaton: Example

Let Σ = {a, b}.

Let a Deterministic Büchi Automaton (DBA) A

be

With F = {s

} the automaton recognizes words with infinitely many a’s.

With F = {s

} the automaton recognizes words with infinitely many b’s.

7 / 69

Büchi Automaton: Example (2)

Let a Nondeterministic Büchi Automaton (NBA) A

be

With F = {s

}, the automaton A

recognizes words with finitely

many a. Thus, L(A

) = L(A

).

Deterministic vs. Nondeterministic Büchi Automata

Theorem

DBAs are strictly less powerful than NBAs.

The subset construction does not work!

Let DA

be

DA

is not equivalent to A

(e.g., it recognizes (b.a)

)

There is no DBA equivalent to A

9 / 69

Closure Properties

Theorem (union, intersection)

For the NBAs A

, A

we can construct

the NBA A s.t. L(A) = L(A

) ∪ L(A

). |A| = |A

| + |A

|

the NBA A s.t. L(A) = L(A

) ∩ L(A

). |A| ≤ |A

| · |A

| · 2.

Union of two NBAs

Definition: union of NBAs

Let A

= (Q

, Σ

, δ

, I

, F

), A

= (Q

, Σ

, δ

, I

, F

).

Then A = A

∪ A

= (Q, Σ, δ, I, F ) is defined as follows Q := Q

∪ Q

, I := I

∪ I

, F := F

∪ F

R(s, s

) :=

 R

(s, s

) if s ∈ Q

R

(s, s

) if s ∈ Q

Theorem

L(A) = L(A

) ∪ L(A

)

|A |= |A

| + |A

|

Note

A is an automaton which just runs nondeterministically either A

or A

(same construction as with ordinary automata)

11 / 69

Synchronous Product of NBAs

Definition: synchronous product of NBAs

Let A

= (Q

, Σ, δ

, I

, F

) and A

= (Q

, Σ, δ

, I

, F

).

Then, A

× A

= (Q, Σ, δ, I, F ), where Q = Q

× Q

× {1, 2}.

I = I

× I

× {1}.

F = F

× Q

× {1}.

hp, q, 1i −→ hp

, q

, 1i iff p −→ p

and q −→ q

and p 6∈ F

. hp, q, 1i −→ hp

, q

, 2i iff p −→ p

and q −→ q

and p ∈ F

. hp, q, 2i −→ hp

, q

, 2i iff p −→ p

and q −→ q

and q 6∈ F

. hp, q, 2i −→ hp

, q

, 1i iff p −→ p

and q −→ q

and q ∈ F

.

Theorem

L(A

× A

) = L(A

) ∩ L(A

).

|A

× A

| ≤ 2 · |A

| · |A

|.

Synchronous Product of NBAs: Intuition

The automaton remembers two tracks, one for each source NBA, and it points to one of the two tracks

As soon as it goes through an accepting state of the current track, it switches to the other track

=⇒ in order to visit infinitely often a state in F (i.e., F

), it must visit infinitely often some state also in F

Important subcase: If F

= Q

, then Q = Q

× Q

.

I = I

× I

. F = F

× Q

.

13 / 69

Synchronous Product of NBAs: Example

Closure Properties (2)

Theorem (complementation) [Safra, MacNaughten]

For the NBA A

we can construct an NBA A

such that L(A

) = L(A

).

|A

| = O(2

).

Method: (hint)

(i) convert a Büchi automaton into a Non-Deterministic Rabin automaton

(ii) determinize and Complement the Rabin automaton (iii) convert the Rabin automaton into a Büchi automaton.

15 / 69

Generalized Büchi Automaton

Definition

A Generalized Büchi Automaton is a tuple A := (Q, Σ, δ, I, FT ) where FT = hF

, F

, . . . , F

i with F

⊆ Q.

A run ρ of A is accepting if Inf (ρ) ∩ F

6= ∅ for each 1 ≤ i ≤ k .

Theorem

For every Generalized Büchi Automaton we can construct a language equivalent plain Büchi Automaton.

Intuition

Let Q

= Q × {1, . . . , K }.

The automaton remains in phase i till it visits a state in F

. Then, it

moves to (i mod K ) + 1 mode.

De-generalization of a generalized NBA

Definition: De-generalization of a generalized NBA

Let A

= (Q, Σ, δ, I, FT ) a generalized BA s.f. FT

= {F

, ..., F

}.

Then a language-equivalent BA A

= (Q

, Σ, δ

, I

, F

) is built as follows

Q

= Q

× {1, ..., K }.

I

= I × {1}.

F

= F

× {1}.

δ

is s.t., for every i ∈ [1, ..., K ]:

hp, ii −→ hq, ii

iff p −→ q ∈ δ and p 6∈ F

. hp, ii −→ hq, (i mod K ) + 1i iff p

−→ q ∈ δ and p ∈ F

.

Theorem

L(A

) = L(A).

|A

| ≤ K · |A|.

17 / 69

Degeneralizing a Büchi automaton: Example

Omega-regular Expressions

Definition

A language is called ω-regular if it has the form ∪

U

.(V

)

where U

, V

are regular languages.

Theorem

A language L is ω-regular iff it is NBA-recognizable.

19 / 69

Outline

1

Büchi Automata

2

The Automata-Theoretic Approach to LTL Reasoning General Ideas

Language-Emptiness Checking of Büchi Automata From Kripke Models to Büchi Automata

From LTL Formulas to Büchi Automata Complexity

3

Exercises

Outline

1

Büchi Automata

2

The Automata-Theoretic Approach to LTL Reasoning General Ideas

Language-Emptiness Checking of Büchi Automata From Kripke Models to Büchi Automata

From LTL Formulas to Büchi Automata Complexity

3

Exercises

21 / 69

Automata-Theoretic LTL Satisfiability and Entailment

LTL Validity/Satisfiability Let ψ be an LTL formula

|= ψ (LTL)

⇐⇒ ¬ψ unsat

⇐⇒ L(A_¬ψ) = ∅

A

is a Büchi Automaton which represents all and only the paths that satisfy ¬ψ (do not satisfy ψ)

LTL Entailment

Let ϕ, ψ be an LTL formula

|= ϕ → ψ (LTL)

⇐⇒ ϕ ∧ ¬ψunsat

⇐⇒ L(Aϕ∧¬ψ) = ∅

A

is a Büchi Automaton which represents all and only the

paths that satisfy ϕ ∧ ¬ψ (satisfy ϕ and do not satisfy ψ)

Automata-Theoretic LTL Model Checking

LTL Model Checking

Let M be a Kripke model and ψ be an LTL formula

⇐⇒ L(M) ⊆ L(ψ)

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

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

⇐⇒ L(A_M) ∩ L(A¬ψ) = ∅

⇐⇒ L(A_M× A¬ψ) = ∅

A

is a Büchi Automaton equivalent to M (which represents all and only the executions of M)

A

is a Büchi Automaton which represents all and only the paths that satisfy ¬ψ (do not satisfy ψ)

=⇒ A

× A

represents all and only the paths appearing in M and not in ψ.

23 / 69

Automata-Theoretic LTL Model Checking

Four steps Let ϕ

= ¬ψ:

(i) Compute A

(ii) Compute A

(iii) Compute the product A

× A

(iv) Check the emptiness of L(A

× A

)

Outline

1

Büchi Automata

2

The Automata-Theoretic Approach to LTL Reasoning General Ideas

Language-Emptiness Checking of Büchi Automata From Kripke Models to Büchi Automata

From LTL Formulas to Büchi Automata Complexity

3

Exercises

25 / 69

NBA emptiness checking

Find an accepting cycle reachable from an initial state.

A naive algorithm:

(i) a DFS finds the final states f reachable from an initial state;

(ii) for each f , a second DFS finds if it can reach f (i.e., if there exists a loop)

Complexity: O(n

) SCC-based algorithm:

(i) Tarjan’s algorithm uses a DFS to find the SCCs in linear time;

(ii) drop all SCCs which do not have at least one arc, and which do not contain at least one accepting state f

(iii) another DFS finds if the union of non-trivial SCCs is reachable from an initial state.

Complexity: O(n)

Drawbacks: it stores too much information and does not find

directly a counterexample.

Double Nested DFS algorithm

Double Nested DFS Two nested DFSs

DFS1finds the final states f reachable from an initial state for each f, DFS2 finds if it can reach f (i.e., if there exists a loop)

Two Hash tables:

T1: reachable states

T2: states reachable from a reachable final state

Two stacks:

S1: current branch of states reachable

S2: current branch of states reachable from final state f

It stops as soon as it finds a counterexample.

The counterexample is given by

the stack of DFS2 (an accepting, preceded by cycle) the stack of DFS1 (a path from an initial state to the cycle)

DFS1 invokes DFS2 on each f

only after popping it (postorder) T2 passed by reference, is not reset at each call of DFS2 !

27 / 69

Double Nested DFS - First DFS

// returns True if empty language, false otherwise Bool DFS1(NBA A) {

stack S1=I; stack S2=∅;

Hashtable T1=I; Hashtable T2=∅;

while S1!=∅ { v=top(S1);

if ∃w s.t. w∈ δ(v) && T1(w)==0 { hash(w,T1);

push(w,S1);

} else { pop(S1);

if (v∈F && !DFS2(v,S2,T2,A)) return False;

} }

return True;

}

Double Nested DFS - Second DFS

Bool DFS2(state f, stack & S, Hashtable & T, NBA A) { hash(f,T);

S = {f}

while S!=∅ { v=top(S);

if f∈ δ(v) return False;

if ∃w s.t. w∈ δ(v) && T(w)==0 { hash(w);

push(w);

} else pop(S);

}

return True;

}

Remark: T passed by reference, is not reset at each call of DFS2 !

29 / 69

Double nested DFS: intuition

DFS1 invokes DFS2 on each f

, ..., f

only after popping it (postorder):

suppose DFS2 is invoked on f

before than on f

=⇒ f

not reachable from (any state s which is reachable from) f

If during DFS2(f

, ...) it is encountered a state S which has already been explored by DFS2(f

, ...) for some f

,

can we reach f_i from S?

No, because f_i is not reachable from f_j!

=⇒ it is safe to backtrack.

Double nested DFS: intuition

DFS1 invokes DFS2 on each f

, ..., f

only after popping it (postorder):

suppose DFS2 is invoked on f

before than on f

=⇒ f

not reachable from (any state s which is reachable from) f

If during DFS2(f

, ...) it is encountered a state S which has already been explored by DFS2(f

, ...) for some f

,

can we reach f_i from S?

No, because f_i is not reachable from f_j!

=⇒ it is safe to backtrack. f

f

S

30 / 69

Double nested DFS: intuition

DFS1 invokes DFS2 on each f

, ..., f

only after popping it (postorder):

suppose DFS2 is invoked on f

before than on f

=⇒ f

not reachable from (any state s which is reachable from) f

If during DFS2(f

, ...) it is encountered a state S which has already been explored by DFS2(f

, ...) for some f

,

can we reach f_i from S?

No, because f_i is not reachable from f_j!

=⇒ it is safe to backtrack. f

f

S

Double nested DFS: intuition

DFS1 invokes DFS2 on each f

, ..., f

only after popping it (postorder):

suppose DFS2 is invoked on f

before than on f

=⇒ f

not reachable from (any state s which is reachable from) f

If during DFS2(f

, ...) it is encountered a state S which has already been explored by DFS2(f

, ...) for some f

,

can we reach f_i from S?

No, because f_i is not reachable from f_j!

=⇒ it is safe to backtrack. f

f

S

30 / 69

Double nested DFS: intuition

DFS1 invokes DFS2 on each f

, ..., f

only after popping it (postorder):

suppose DFS2 is invoked on f

before than on f

=⇒ f

not reachable from (any state s which is reachable from) f

If during DFS2(f

, ...) it is encountered a state S which has already been explored by DFS2(f

, ...) for some f

,

can we reach f_i from S?

No, because f_i is not reachable from f_j!

=⇒ it is safe to backtrack. f

f

S

???

Double nested DFS: intuition

DFS1 invokes DFS2 on each f

, ..., f

only after popping it (postorder):

suppose DFS2 is invoked on f

before than on f

=⇒ f

not reachable from (any state s which is reachable from) f

If during DFS2(f

, ...) it is encountered a state S which has already been explored by DFS2(f

, ...) for some f

,

can we reach f_i from S?

No, because f_i is not reachable from f_j!

=⇒ it is safe to backtrack. f

f

S

30 / 69

Double nested DFS: intuition

DFS1 invokes DFS2 on each f

, ..., f

only after popping it (postorder):

suppose DFS2 is invoked on f

before than on f

=⇒ f

not reachable from (any state s which is reachable from) f

If during DFS2(f

, ...) it is encountered a state S which has already been explored by DFS2(f

, ...) for some f

,

can we reach f_i from S?

No, because f_i is not reachable from f_j!

=⇒ it is safe to backtrack. f

f

S

Double Nested DFS: example

T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

3

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

4

0 1

4 3

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

0 1

4 3

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

3

0 1

3

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

4

0 1

4 3

0 1

3

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

0 1

4 3

0 1

3

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

0 1

4

0 1

3

0 1

4

00 11

3 2

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

5

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

6

00 11

6 5

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

00 11

6 5

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

2

0 1

2 5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

0 1

2 5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Double Nested DFS: example

6

0 1

6

0 1

2 5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5

T2

Double Nested DFS: example

1

0 1

1 6

0 1

6

0 1

2 5

0 1

5

00 11

6

00 11

5

0 1

4

0 1

3

0 1

4

00 11

3

0 1

2 1

0 1

1 T1

S2 S1

3

4 2

1 6

5 T2

31 / 69

Outline

1

Büchi Automata

2

The Automata-Theoretic Approach to LTL Reasoning General Ideas

Language-Emptiness Checking of Büchi Automata From Kripke Models to Büchi Automata

From LTL Formulas to Büchi Automata Complexity

3

Exercises

Computing an NBA A

from a Kripke Structure M

Transform a Kripke model M = hS, S

, R, L, APi into an NBA A

= hQ, Σ, δ, I, F i s.t.:

States:Q := S ∪ {init}, init being a new initial state Alphabet:Σ :=2^AP

Initial State:I := {init}

Accepting States:F := Q = S ∪ {init}

Transitions:

δ : q−→ q^{a 0}iff (q, q⁰) ∈R and L(q⁰) =a init−→ q iff q ∈ S^a ₀and L(q) = a

L(A

) = L(M)

|A

| = |M| + 1

33 / 69

Computing a NBA A

from a Kripke Structure M:

Example

{p,q}

{p,q}

{p,q}

Kripke Structure Buechi Automaton

{p,q} {p}

{q}

{p,−q}

{p,−q}

{−p,q}

=⇒ Substantially, add one initial state, move labels from states to

incoming edges, set all states as accepting states

Labels on Kripke Structures and BA’s - Remark

Note that the labels of a Büchi Automaton are different from the labels of a Kripke Structure. Also graphically, they are interpreted differently:

p

in a Kripke Structure, it means that p is true and all other propositions are false;

in a Büchi Automaton, it means that p is true and all other propositions are irrelevant (“don’t care”), i.e. they can be either true or false.

35 / 69

Outline

1

Büchi Automata

2

The Automata-Theoretic Approach to LTL Reasoning General Ideas

Language-Emptiness Checking of Büchi Automata From Kripke Models to Büchi Automata

From LTL Formulas to Büchi Automata Complexity

3

Exercises

Translation problem

Problem

Given an LTL formula φ, find a Büchi Automaton that accepts the same language of φ.

It is a fundamental problem in LTL model checking (in other words, every model checking algorithm that verifies the correctness of an LTL formula translates it in some sort of finite-state machine).

We will translate an LTL formula into a Generalized Büchi Automata (GBA).

37 / 69

LTL Negative Normal Form (NNF)

Every LTL formula ϕ can be written into an equivalent formula ϕ

using only the operators ∧, ∨, X, U, R on propositional literals.

Done by pushing negations down to literal level:

¬(ϕ

∨ ϕ

) =⇒ (¬ϕ

∧ ¬ϕ

)

¬(ϕ

∧ ϕ

) =⇒ (¬ϕ

∨ ¬ϕ

)

¬Xϕ

=⇒ X¬ϕ

¬(ϕ

Uϕ

) =⇒ (¬ϕ

R¬ϕ

)

¬(φ

Rφ

) =⇒ (¬φ

U¬φ

)

=⇒ the resulting formula is expressed in terms of ∨, ∧, X , U, R and literals (Negative Normal Form, NNF).

encoding linear if a DAG representation is used

In the construction of A

we now assume that ϕ is in NNF.

For convenience, we still use F’s and G’s as shortcuts:

Fϕ for >Uϕ and Gϕ for ⊥Rϕ

On-the-fly Construction of A

(Intuition)

Apply recursively the following steps:

Step 1: Apply the tableau expansion rules to ϕ

ψ

Uψ

=⇒ ψ

∨ (ψ

∧ X(ψ

Uψ

)) [and Fψ =⇒ ψ ∨ XFψ]

ψ

Rψ

=⇒ ψ

∧ (ψ

∨ X(ψ

Rψ

)) [and Gψ =⇒ ψ ∧ XGψ]

until we get a Boolean combination of elementary subformulas of ϕ (An elementary formula is a proposition or a X-formula.)

39 / 69

Tableaux Rules: a Quote

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

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

On-the-fly Construction of A

(Intuition) [cont.]

Step 2: Convert all formulas into Disjunctive Normal Form, and then push the conjunctions inside the next:

ϕ =⇒ _

i

( ^

j

l

∧ ^

k

Xψ

) =⇒ _

i

( ^

j

l

∧ X ^

k

ψ

).

Each disjunct (

labels

z }| {

^

j

l

∧

next part

z }| {

X ^

k

ψ

) represents a state:

the conjunction of literalsV

jl_ij representsa set of labels in Σ (e.g., if Vars(ϕ) = {p, q, r }, p ∧ ¬q represents the two labels {p, ¬q, r } and {p, ¬q, ¬r } )

XV

kψ_ikrepresents thenext partof the state (obbligations for the successors)

N.B., if no next part occurs, X> is implicitly assumed

41 / 69

On-the-fly Construction of A

(Intuition) [cont.]

Step 3: For every state S

represented by ( V

j

l

∧ X

ϕi

z }| {

^

k

ψ

) label the incoming edges of S

with V

j

l

mark that the state S

satisfies ϕ

apply recursively steps 1-2-3 to ϕ

= V

k

ψ

,

i⁰(V

jl_i⁰0j∧ XV

kψ_i⁰0k) from each disjunct(V

jl_i⁰0j ∧ XV

kψ_i⁰0k)generate a new state Sii⁰ (if not already present) and label it as satisfying ϕ_i ^def=V

kψ_ik

draw an edge from S

to all states S

which satisfy V

k

ψ

(if no next part occurs, X> is implicitly assumed, so that an edge

to a “true” node is drawn)

On-the-fly Construction of A

(Intuition) [cont.]

ϕ??

43 / 69

On-the-fly Construction of A

(Intuition) [cont.]

W

i(V

jlij∧ XV

kψik)!

On-the-fly Construction of A

(Intuition) [cont.]

(V

jl1j∧ XV

kψ1k)

(V

jl_2j∧ XV

kψ2k)

(V

jlij∧ XV

kψik)

...

W

i(V

jlij∧ XV

kψik)!

43 / 69

On-the-fly Construction of A

(Intuition) [cont.]

V

jl1j [V

kψ1k]

[V

kψ2k] V

jl2j

[V

kψik] V

jlij

(V

jl1j∧ XV

kψ1k)

(V

jl_2j∧ XV

kψ2k)

(V

jlij∧ XV

kψik)

...

W

i(V

jlij∧ XV

kψik)!

On-the-fly Construction of A

(Intuition) [cont.]

...

V

kψik ?

43 / 69

On-the-fly Construction of A

(Intuition) [cont.]

...

W

i(V

jlij∧ XV

kψik)!

V

jl₁⁰0j

V

jl₂⁰0j

V

jl_i⁰0j [V

kψ⁰_ik] [V

kψ⁰_2k] [V

kψ⁰_1k] W

i⁰ (V

jl_i⁰0j∧ XV

kψ⁰_i0k)

....

On-the-fly Construction of A

(Intuition) [cont.]

V

jl1j

V

jl2j

V

jlij

...

W

i(V

jlij∧ XV

kψik)!

V

jl₁⁰0j

V

jl₂⁰0j

V

jl_i⁰0j [V

kψ⁰_ik] [V

kψ⁰_2k] [V

kψ⁰_1k]

....

43 / 69

On-the-fly Construction of A

(Intuition) [cont.]

When the recursive applications of steps 1-3 has terminated and the automata graph has been built, then apply the following:

Step 4: For every ψ

Uϕ

, for every state q

, mark q

with F

iff (ψ

Uϕ

) / ∈ q

or ϕ

∈ q

(If there is no U-subformulas, then mark all states with F

—i.e., FT

= {Q}).

Remark

The fact that we initially converted the formula into NNF guarantees

that only positive U/F-subformulas and negative R-/G-subformulas

are considered here

Dealing with U-subformulas: Intuition

Tableaux rules: ϕ

Uϕ

⇐⇒ (ϕ

∨ (ϕ

∧ Xϕ

Uϕ

)) are a property, not a definition of U:

=⇒ they implicitly admit a “weaker” semantics of ϕ

Uϕ

, in which ϕ

Uϕ

always holds and ϕ

never holds

It cannot happen that we get into a state s

from which we can enter a path π

in which ϕ

Uϕ

holds forever and ϕ

never holds.

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2

ϕ1Uϕ2 ϕ1Uϕ2

−ϕ2 . . . .

−ϕ2 −ϕ2

=⇒ every legal path must touch infinitely often a state where

¬(ϕ

Uϕ

) ∨ ϕ

) holds

In LTL: GF(¬(ϕ

Uϕ

) ∨ ϕ

) (“avoid bad loop”)

45 / 69

On-the-fly Construction of A

- State

Henceforth, a state is represented by a tuple s := hλ, χ, σi where:

λis the set of labels

χis the next part, i.e. the set of X -formulas satisfied by s σis the set of the subformulas of φ satisfied by s (necessary for the fairness definition)

Given a set of LTL formulas Ψ

= {ψ

, ..., ψ

}, we define

Cover (Ψ)

= Expand (Ψ, h∅, ∅, ∅i) to be the set of initial states of the Buchi automaton representing V

j

ψ

.

On-the-fly Construction of A

- Expand

Given a set of formulas Φ to expand and a state s, we define the set of states Expand (Φ, s) recursively as follows:

if Φ = ∅, Expand (Φ, s) = {s}

if ⊥ ∈ Φ, Expand (Φ, s) = ∅ if > ∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) = Expand (Φ\{>}, hλ, χ, σ ∪ {>}i) if l ∈ Φ and s = hλ, χ, σi, l propositional literal Expand (Φ, s) = Expand (Φ\{l}, hλ ∪ {l}, χ, σ ∪ {l}i) (add l to the labels of s and to set of satisfied formulas) if Xψ ∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) = Expand (Φ\{X ψ}, hλ, χ ∪ {ψ}, σ ∪ {Xψ}i) (add ψ to the next part of s and Xψ to set of satisfied formulas) if ψ

∧ ψ

∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =

Expand (Φ ∪ {ψ

, ψ

}\{ψ

∧ ψ

}, hλ, χ, σ ∪ {ψ

∧ ψ

}i) (process both ψ

and ψ

and add ψ

∧ ψ

to σ)

...

47 / 69

On-the-fly Construction of A

- Expand

if ψ

∨ ψ

∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ ∪ {ψ

}\{ψ

∨ ψ

}, hλ, χ, σ ∪ {ψ

∨ ψ

}i)

∪Expand (Φ ∪ {ψ

}\{ψ

∨ ψ

}, hλ, χ, σ ∪ {ψ

∨ ψ

}i) (split s in two copies, process ψ

on the first, ψ

on the second, add ψ

∨ ψ

to σ)

if ψ

Uψ

∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ ∪ {ψ₁}\{ψ₁Uψ₂}, hλ, χ ∪ {ψ₁Uψ₂}, σ ∪ {ψ₁Uψ₂}i)

∪Expand (Φ ∪ {ψ₂}\{ψ₁Uψ₂}, hλ, χ, σ ∪ {ψ₁Uψ₂}i)

(split s in two copies and process ψ

on the first, ψ

on the second, add ψ

Uψ

to σ)

if ψ

Rψ

∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ ∪ {ψ₂}\{ψ₁Rψ₂}, hλ, χ ∪ {ψ₁Rψ₂}, σ ∪ {ψ₁Rψ₂}i)

∪Expand (Φ ∪ {ψ₁, ψ₂}\{ψ₁Rψ₂}, hλ, χ, σ ∪ {ψ₁Rψ₂}i)

(split s in two copies and process ψ

on the first, ψ

on the

second, add ψ

Rψ

to σ)

On-the-fly Construction of A

- Expand

Two relevant subcases: Fψ

= >Uψ and Gψ

= ⊥Rψ if Fψ ∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ\{Fψ}, hλ, χ ∪ {Fψ}, σ ∪ {Fψ}i)

∪Expand (Φ ∪ {ψ}\{Fψ}, hλ, χ, σ ∪ {Fψ}i)

if Gψ ∈ Φ and s = hλ, χ, σi,

Expand (Φ, s) =Expand (Φ ∪ {ψ}\{Gψ}, hλ, χ ∪ {Gψ}, σ ∪ {Gψ}i) Note: Expand (Φ ∪ {⊥, ψ}\{Gψ}, ...) = ∅

49 / 69

Definition of A

Given a set of LTL formulas Ψ, we define Cover (Ψ)

= Expand (Ψ, h∅, ∅, ∅i).

For an LTL formula φ, we construct a Generalized NBA A

= (Q, Σ, δ, I, FT ) as follows:

Σ = 3

(v ∈ {>, ⊥, ∗}) Q is the smallest set such that

Cover ({φ}) ⊆ Q

ifhλ, χ, σi ∈ Q, thenCover (χ) ∈ Q

Q

= Cover ({φ}).

s

0

−→ s

∈ δ iff, s = hλ, χ, σi, s

= hλ

, χ

, σ

i and s

∈ Cover (χ) FT = hF

, F

, ..., F

i where, for all (ψ

Uφ

) occurring positively in φ, F

= {hλ, χ, σi ∈ Q | (ψ

Uφ

) / ∈ σ or φ

∈ σ}.

(If there is no U-subformulas, then FT

= {Q}).

Example: φ = FGp

Cover ({FGp})

= Expand ({FGp}, h∅, ∅, ∅i)

= Expand (∅, h∅, {FGp}, {FGp}i) ∪ Expand ({Gp}, h∅, ∅, {FGp}i)

= {h∅, {FGp}, {FGp}i} ∪ Expand ({p}, h∅, {Gp}, {FGp, Gp}i)

= {h∅, {FGp}, {FGp}i} ∪ Expand (∅, h{p}, {Gp}, {FGp, Gp, p}i)

= {h∅, {FGp}, {FGp}i, h{p}, {Gp}, {FGp, Gp, p}i}

Cover ({Gp}) = Expand ({Gp}, h∅, ∅, ∅i)

= Expand ({p}, h∅, {Gp}, {Gp}i)

= Expand (∅, h{p}, {Gp}, {Gp, p}i)

= {h{p}, {Gp}, {Gp, p}i}

Optimization:

merge h{p}, {Gp}, {FGp, Gp, p}i and h{p}, {Gp}, {Gp, p}i

51 / 69

Example: φ = FGp

Call s

= h∅, {FGp}, {FGp}i, s

= h{p}, {Gp}, {FGp, Gp, p}i Q = {s

, s

}

Q

= {s

, s

}.

T : s

→ {s

, s

}, s

→ {s

}

FT = hF

i where F

= {s

}.

[ XGp ]

p

p

p

Example: φ = pUq

Cover ({pUq})

= Expand ({pUq}, h∅, ∅, ∅i)

= Expand ({p}, h∅, {pUq}, {pUq}i) ∪ Expand ({q}, h∅, ∅, {pUq}i)

= Expand (∅, h{p}, {pUq}, {pUq, p}i) ∪ Expand (∅, h{q}, ∅, {pUq, q}i)

= {h{p}, {pUq}, {pUq, p}i} ∪ {h{q}, {>}, {pUq, q}i}

Cover ({>}) = {h∅, {>}, {>}i}

53 / 69

Example: φ = pUq

Let s

=

h{p}, {pUq}, {pUq, p}i, s

=

h{q}, {>}, {pUq, q}i, s

=

h∅, {>}, {>}i.

Q = {s

, s

, s

}, Q

= {s

, s

},

T : s

→ {s

, s

}, s

→ {s

} s

→ {s

}

FT = hF

i where F

= {s

, s

}.

[ XT ]

q

q p

p

Example: φ = GFp

Cover ({GFp})

= E ({GFp}, h∅, ∅, ∅i)

= E ({Fp}, h∅, {GFp}, {GFp}i)

= E ({}, h∅, {GFp, Fp}, {GFp, Fp}i) ∪ E ({p}, h{}, {GFp}, {GFp, Fp}i)

= E ({}, h∅, {GFp, Fp}, {GFp, Fp}i) ∪ E ({}, h{p}, {GFp}, {GFp, Fp, p}i)

= {h∅, {GFp, Fp}, {GFp, Fp}i} ∪ {h{p}, {GFp}, {GFp, Fp, p}i}

Note: GFp ∧ Fp ⇐⇒ GFp, s.t. Cover (GFp ∧ Fp) = Cover (GFp)

55 / 69

Example: GFp

Let s

=

h{p}, {GFp}, {GFp, Fp, p}i, s

=

h∅, {GFp, Fp}, {GFp, Fp}i, Q = {s

, s

},

Q

= {s

, s

}, T : s

→ {s

, s

},

s

→ {s

, s

}

FT = hF

i where F

= {s

}.

[ XGFp ] [ XGFp ]

p

p

p

NBAs of disjunctions of formulas

Remark

If ϕ

= (ϕ

∨ ϕ

) and A

, A

are NBAs encoding ϕ

and ϕ

resp., then L(ϕ) = L(ϕ

) ∪ L(ϕ

), so that A

= A

∪ A

is an NBA encoding ϕ

A

non necessarily the smallest/best NBA encoding ϕ Example

Let ϕ

= (GFp → GFq), i.e., ϕ ≡ (FG¬p ∨ GFq).

Then A

∪ A

encodes ϕ:

¬p

¬p q

q q

¬p

57 / 69

Suggested Exercises:

Find an NBA encoding:

p

(p ∧ q) ∨ (¬p ∧ ¬q) Fp

Gp pRq

(GFp ∧ GFq) → Gr

Outline

1

Büchi Automata

2

The Automata-Theoretic Approach to LTL Reasoning General Ideas

Language-Emptiness Checking of Büchi Automata From Kripke Models to Büchi Automata

From LTL Formulas to Büchi Automata Complexity

3

Exercises

59 / 69

Automata-Theoretic LTL Model Checking: Complexity

Four steps:

(i) Compute A

:

|A

| = O(|M|) (ii) Compute A

:

|A

| = O(2

)

(iii) Compute the product A

× A

:

|A

× A

| = |A

| · |A

| = O(|M| · 2

) (iv) Check the emptiness of L(A

× A

):

O(|A

× A

|) = O(|M| · 2

)

=⇒ The complexity of LTL M.C. grows linearly wrt. the size of the

model M and exponentially wrt. the size of the property ϕ

Final Remarks

Büchi automata are in general more expressive than LTL!

=⇒ some tools (e.g., Spin) allow specifications to be expressed directly as NBAs

=⇒ complementation of NBA important!

For every LTL formula, there are many possible equivalent NBAs

=⇒ lots of research for finding “the best” conversion algorithm Performing the product and checking emptiness very relevant

=⇒ lots of techniques developed (e.g., partial order reduction)

=⇒ lots on ongoing research

61 / 69