Introduction to Formal Methods Chapter 08: Automata-theoretic LTL Model Checking

Introduction to Formal Methods

Chapter 08: Automata-theoretic LTL Model Checking

Roberto Sebastiani and Stefano Tonetta

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

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

CDLM in Informatica, academic year 2019-2020

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

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

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

Outline

1 Background: Finite-Word Automata Language Containment

Automata on Finite Words

2 Infinite-Word Automata Automata on Infinite Words Emptiness Checking

3 The Automata-Theoretic Approach to Model Checking Automata-Theoretic LTL Model Checking

From Kripke Structures to Büchi Automata

From LTL Formulas to Büchi Automata: generalities On-the-fly construction of Bu¨chi Automata from LTL Complexity

4 Exercises

Outline

1 Background: Finite-Word Automata Language Containment

Automata on Finite Words

2 Infinite-Word Automata Automata on Infinite Words Emptiness Checking

3 The Automata-Theoretic Approach to Model Checking Automata-Theoretic LTL Model Checking

From Kripke Structures to Büchi Automata

From LTL Formulas to Büchi Automata: generalities On-the-fly construction of Bu¨chi Automata from LTL Complexity

4 Exercises

Outline

1 Background: Finite-Word Automata Language Containment

Automata on Finite Words

2 Infinite-Word Automata Automata on Infinite Words Emptiness Checking

3 The Automata-Theoretic Approach to Model Checking Automata-Theoretic LTL Model Checking

From Kripke Structures to Büchi Automata

From LTL Formulas to Büchi Automata: generalities On-the-fly construction of Bu¨chi Automata from LTL Complexity

4 Exercises

System’s computations

The behaviors (computations) of a system can be seen as sequences of assignments to propositions.

MODULE main

VAR done: Boolean;

ASSIGN

init(done):=0;

next(done):= case

!done: {0,1};

done: done;

esac;

Since the state space is finite, the set of computations can be

represented by a finite automaton.

System’s computations

The behaviors (computations) of a system can be seen as sequences of assignments to propositions.

MODULE main

VAR done: Boolean;

ASSIGN

init(done):=0;

next(done):= case

!done: {0,1};

done: done;

esac;

Since the state space is finite, the set of computations can be represented by a finite automaton.

or

!done done

done

Correct computations

Some computations are correct and others are not acceptable.

We can build an automaton for the set of all acceptable computations.

Example: eventually, done will be true forever (FGdone).

Language Containment Problem

Solution to the verification problem

=⇒ Check if language of the system automaton is contained in the language accepted by the property automaton.

The language containment problem is the problem of deciding if a language is a subset of another language.

L(A ₁ ) ⊆ L(A ₂ ) ⇐⇒ L(A ₁ ) ∩ L(A ₂ ) = {}

In order to solve the language containment problem, we need to know:

(i) how to complement an automaton, (ii) how to intersect two automata,

(iii) how to check the language emptiness of an automaton.

Language Containment Problem

Solution to the verification problem

=⇒ Check if language of the system automaton is contained in the language accepted by the property automaton.

The language containment problem is the problem of deciding if a language is a subset of another language.

L(A ₁ ) ⊆ L(A ₂ ) ⇐⇒ L(A ₁ ) ∩ L(A ₂ ) = {}

In order to solve the language containment problem, we need to know:

(i) how to complement an automaton, (ii) how to intersect two automata,

(iii) how to check the language emptiness of an automaton.

Language Containment Problem

Solution to the verification problem

=⇒ Check if language of the system automaton is contained in the language accepted by the property automaton.

The language containment problem is the problem of deciding if a language is a subset of another language.

L(A ₁ ) ⊆ L(A ₂ ) ⇐⇒ L(A ₁ ) ∩ L(A ₂ ) = {}

In order to solve the language containment problem, we need to know:

(i) how to complement an automaton, (ii) how to intersect two automata,

(iii) how to check the language emptiness of an automaton.

Language Containment Problem

Solution to the verification problem

=⇒ Check if language of the system automaton is contained in the language accepted by the property automaton.

The language containment problem is the problem of deciding if a language is a subset of another language.

L(A ₁ ) ⊆ L(A ₂ ) ⇐⇒ L(A ₁ ) ∩ L(A ₂ ) = {}

In order to solve the language containment problem, we need to know:

(i) how to complement an automaton, (ii) how to intersect two automata,

(iii) how to check the language emptiness of an automaton.

Language Containment Problem

Solution to the verification problem

=⇒ Check if language of the system automaton is contained in the language accepted by the property automaton.

The language containment problem is the problem of deciding if a language is a subset of another language.

L(A ₁ ) ⊆ L(A ₂ ) ⇐⇒ L(A ₁ ) ∩ L(A ₂ ) = {}

In order to solve the language containment problem, we need to know:

(i) how to complement an automaton, (ii) how to intersect two automata,

(iii) how to check the language emptiness of an automaton.

Language Containment Problem

Solution to the verification problem

=⇒ Check if language of the system automaton is contained in the language accepted by the property automaton.

The language containment problem is the problem of deciding if a language is a subset of another language.

L(A ₁ ) ⊆ L(A ₂ ) ⇐⇒ L(A ₁ ) ∩ L(A ₂ ) = {}

In order to solve the language containment problem, we need to know:

(i) how to complement an automaton, (ii) how to intersect two automata,

(iii) how to check the language emptiness of an automaton.

Outline

1 Background: Finite-Word Automata Language Containment

Automata on Finite Words

2 Infinite-Word Automata Automata on Infinite Words Emptiness Checking

3 The Automata-Theoretic Approach to Model Checking Automata-Theoretic LTL Model Checking

From Kripke Structures to Büchi Automata

From LTL Formulas to Büchi Automata: generalities On-the-fly construction of Bu¨chi Automata from LTL Complexity

4 Exercises

Finite Word Languages

An Alphabet Σ is a collection of symbols (letters).

E.g. Σ = {a, b}.

A finite word is a finite sequence of letters. (E.g. aabb.) The set of all finite words is denoted by Σ ^∗ .

A language U is a set of words, i.e. U ⊆ Σ ^∗ .

Example: Words over Σ = {a, b} with equal number of a’s and b’s.

(E.g. aabb or abba.)

Language recognition problem: determine whether a word belongs to a language.

Automata are computational devices able to solve language

recognition problems.

Finite Word Languages

An Alphabet Σ is a collection of symbols (letters).

E.g. Σ = {a, b}.

A finite word is a finite sequence of letters. (E.g. aabb.) The set of all finite words is denoted by Σ ^∗ .

A language U is a set of words, i.e. U ⊆ Σ ^∗ .

Example: Words over Σ = {a, b} with equal number of a’s and b’s.

(E.g. aabb or abba.)

Language recognition problem: determine whether a word belongs to a language.

Automata are computational devices able to solve language

recognition problems.

Finite Word Languages

An Alphabet Σ is a collection of symbols (letters).

E.g. Σ = {a, b}.

A finite word is a finite sequence of letters. (E.g. aabb.) The set of all finite words is denoted by Σ ^∗ .

A language U is a set of words, i.e. U ⊆ Σ ^∗ .

Example: Words over Σ = {a, b} with equal number of a’s and b’s.

(E.g. aabb or abba.)

Language recognition problem: determine whether a word belongs to a language.

Automata are computational devices able to solve language

recognition problems.

Finite Word Languages

An Alphabet Σ is a collection of symbols (letters).

E.g. Σ = {a, b}.

A finite word is a finite sequence of letters. (E.g. aabb.) The set of all finite words is denoted by Σ ^∗ .

A language U is a set of words, i.e. U ⊆ Σ ^∗ .

Example: Words over Σ = {a, b} with equal number of a’s and b’s.

(E.g. aabb or abba.)

Language recognition problem: determine whether a word belongs to a language.

Automata are computational devices able to solve language

recognition problems.

Finite Word Languages

An Alphabet Σ is a collection of symbols (letters).

E.g. Σ = {a, b}.

A finite word is a finite sequence of letters. (E.g. aabb.) The set of all finite words is denoted by Σ ^∗ .

A language U is a set of words, i.e. U ⊆ Σ ^∗ .

Example: Words over Σ = {a, b} with equal number of a’s and b’s.

(E.g. aabb or abba.)

Language recognition problem: determine whether a word belongs to a language.

Automata are computational devices able to solve language

recognition problems.

Finite Word Languages

An Alphabet Σ is a collection of symbols (letters).

E.g. Σ = {a, b}.

A finite word is a finite sequence of letters. (E.g. aabb.) The set of all finite words is denoted by Σ ^∗ .

A language U is a set of words, i.e. U ⊆ Σ ^∗ .

Example: Words over Σ = {a, b} with equal number of a’s and b’s.

(E.g. aabb or abba.)

Language recognition problem: determine whether a word belongs to a language.

Automata are computational devices able to solve language

recognition problems.

Finite-State Automata

Basic model of computational systems with finite memory.

Widely applicable

Embedded System Controllers.

Languages: Ester-el, Lustre, Verilog.

Synchronous Circuits.

Regular Expression Pattern Matching Grep, Lex, Emacs.

Protocols

Network Protocols

Architecture: Bus, Cache Coherence, Telephony,...

Finite-State Automata

Basic model of computational systems with finite memory.

Widely applicable

Embedded System Controllers.

Languages: Ester-el, Lustre, Verilog.

Synchronous Circuits.

Regular Expression Pattern Matching Grep, Lex, Emacs.

Protocols

Network Protocols

Architecture: Bus, Cache Coherence, Telephony,...

Notation

a, b ∈ Σ finite alphabet.

u, v , w ∈ Σ ^∗ finite words.

 empty word.

u.v concatenation.

u ⁱ = u.u. .u repeated i-times.

U, V ⊆ Σ ^∗ Finite word languages.

Finite-State Automata Definition

Definition

A Nondeterministic Finite-State Automaton (NFA) 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 final states.

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

We use q −→ q ^{a 0} to denote (q, a, q ⁰ ) ∈ δ.

Definition

A Deterministic Finite-State Automaton (DFA) is a NFA s.t.:

δ : Q × Σ → Q is a total function

Single initial state I = {q ₀ }.

Finite-State Automata Definition

Definition

A Nondeterministic Finite-State Automaton (NFA) 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 final states.

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

We use q −→ q ^{a 0} to denote (q, a, q ⁰ ) ∈ δ.

Definition

A Deterministic Finite-State Automaton (DFA) is a NFA s.t.:

δ : Q × Σ → Q is a total function

Single initial state I = {q ₀ }.

Regular Languages

A run of NFA A on u = a ₀ , a ₁ , . . . , a _n−1 is a finite sequence of states q ₀ , q ₁ , . . . , q _n s.t. q ₀ ∈ I and q _i −→ q ^a

_i+1 for 0 ≤ i < n.

An accepting run is one where q n ∈ F . The language accepted by A is

L(A) = {u ∈ Σ ^∗ | A has an accepting run on u}

The languages accepted by a NFA are called regular languages.

Regular Languages

A run of NFA A on u = a ₀ , a ₁ , . . . , a _n−1 is a finite sequence of states q ₀ , q ₁ , . . . , q _n s.t. q ₀ ∈ I and q _i −→ q ^a

_i+1 for 0 ≤ i < n.

An accepting run is one where q n ∈ F . The language accepted by A is

L(A) = {u ∈ Σ ^∗ | A has an accepting run on u}

The languages accepted by a NFA are called regular languages.

Regular Languages

A run of NFA A on u = a ₀ , a ₁ , . . . , a _n−1 is a finite sequence of states q ₀ , q ₁ , . . . , q _n s.t. q ₀ ∈ I and q _i −→ q ^a

_i+1 for 0 ≤ i < n.

An accepting run is one where q n ∈ F . The language accepted by A is

L(A) = {u ∈ Σ ^∗ | A has an accepting run on u}

The languages accepted by a NFA are called regular languages.

Regular Languages

A run of NFA A on u = a ₀ , a ₁ , . . . , a _n−1 is a finite sequence of states q ₀ , q ₁ , . . . , q _n s.t. q ₀ ∈ I and q _i −→ q ^a

_i+1 for 0 ≤ i < n.

An accepting run is one where q n ∈ F . The language accepted by A is

L(A) = {u ∈ Σ ^∗ | A has an accepting run on u}

The languages accepted by a NFA are called regular languages.

Finite-State Automata: examples

The DFA A ₁ over Σ = {a, b}:

Recognizes words which do not end in b.

The NFA A ₂ over Σ = {a, b}:

Recognizes words which end in b.

Finite-State Automata: examples

The DFA A ₁ over Σ = {a, b}:

Recognizes words which do not end in b.

The NFA A ₂ over Σ = {a, b}:

Recognizes words which end in b.

Determinisation

Theorem (determinisation)

Given a NFA A we can construct a DFA A ⁰ s.t. L(A) = L(A ⁰ ).

Size: |A ⁰ | = 2 ^O(|A|) .

Each state of A ⁰ corresponds to a set {s ₁ , ..., s _j } of states in A (Q ⁰ ⊆ 2 ^Q ), with the intended meaning that :

A

is in the state {s

, .., s

} if A is in one of the states s

, ..., s

The (unique) initial state is I ⁰ = _def {s _i | s _i ∈ I}

The deterministic transition relation δ ⁰ : 2 ^Q × Σ 7−→ 2 ^Q is {s} −→ {s

| s −→ s

}

{s

, ..., s

, ..., s

} −→

S

j=1

{s

| s

−→ s

} The set of final states F ⁰ is such that

{s 1 , ..., s _n } ∈ F ⁰ iff s _i ∈ F for some i ∈ {1, ..., n}

Determinisation

Theorem (determinisation)

Given a NFA A we can construct a DFA A ⁰ s.t. L(A) = L(A ⁰ ).

Size: |A ⁰ | = 2 ^O(|A|) .

Each state of A ⁰ corresponds to a set {s ₁ , ..., s _j } of states in A (Q ⁰ ⊆ 2 ^Q ), with the intended meaning that :

A

is in the state {s

, .., s

} if A is in one of the states s

, ..., s

The (unique) initial state is I ⁰ = _def {s _i | s _i ∈ I}

The deterministic transition relation δ ⁰ : 2 ^Q × Σ 7−→ 2 ^Q is {s} −→ {s

| s −→ s

}

{s

, ..., s

, ..., s

} −→

S

j=1

{s

| s

−→ s

} The set of final states F ⁰ is such that

{s 1 , ..., s _n } ∈ F ⁰ iff s _i ∈ F for some i ∈ {1, ..., n}

Determinisation

Theorem (determinisation)

Given a NFA A we can construct a DFA A ⁰ s.t. L(A) = L(A ⁰ ).

Size: |A ⁰ | = 2 ^O(|A|) .

Each state of A ⁰ corresponds to a set {s ₁ , ..., s _j } of states in A (Q ⁰ ⊆ 2 ^Q ), with the intended meaning that :

A

is in the state {s

, .., s

} if A is in one of the states s

, ..., s

The (unique) initial state is I ⁰ = _def {s _i | s _i ∈ I}

The deterministic transition relation δ ⁰ : 2 ^Q × Σ 7−→ 2 ^Q is {s} −→ {s

| s −→ s

}

{s

, ..., s

, ..., s

} −→

S

j=1

{s

| s

−→ s

} The set of final states F ⁰ is such that

{s 1 , ..., s _n } ∈ F ⁰ iff s _i ∈ F for some i ∈ {1, ..., n}

Determinisation

Theorem (determinisation)

Given a NFA A we can construct a DFA A ⁰ s.t. L(A) = L(A ⁰ ).

Size: |A ⁰ | = 2 ^O(|A|) .

Each state of A ⁰ corresponds to a set {s ₁ , ..., s _j } of states in A (Q ⁰ ⊆ 2 ^Q ), with the intended meaning that :

A

is in the state {s

, .., s

} if A is in one of the states s

, ..., s

The (unique) initial state is I ⁰ = _def {s _i | s _i ∈ I}

The deterministic transition relation δ ⁰ : 2 ^Q × Σ 7−→ 2 ^Q is {s} −→ {s

| s −→ s

}

{s

, ..., s

, ..., s

} −→

S

j=1

{s

| s

−→ s

} The set of final states F ⁰ is such that

{s 1 , ..., s _n } ∈ F ⁰ iff s _i ∈ F for some i ∈ {1, ..., n}

Determinisation

Theorem (determinisation)

Given a NFA A we can construct a DFA A ⁰ s.t. L(A) = L(A ⁰ ).

Size: |A ⁰ | = 2 ^O(|A|) .

Each state of A ⁰ corresponds to a set {s ₁ , ..., s _j } of states in A (Q ⁰ ⊆ 2 ^Q ), with the intended meaning that :

A

is in the state {s

, .., s

} if A is in one of the states s

, ..., s

The (unique) initial state is I ⁰ = _def {s _i | s _i ∈ I}

The deterministic transition relation δ ⁰ : 2 ^Q × Σ 7−→ 2 ^Q is {s} −→ {s

| s −→ s

}

{s

, ..., s

, ..., s

} −→

S

j=1

{s

| s

−→ s

} The set of final states F ⁰ is such that

{s 1 , ..., s _n } ∈ F ⁰ iff s _i ∈ F for some i ∈ {1, ..., n}

Determinisation [cont.]

NFA A ₂ : Words which end in b.

A ₂ can be determinised into the automaton DA ₂ below.

(#States = 2 ^Q .)

There are NFAs of size n for which the size of the minimum sized

DFA must have size O(2 ⁿ ).

Determinisation [cont.]

NFA A ₂ : Words which end in b.

A ₂ can be determinised into the automaton DA ₂ below.

(#States = 2 ^Q .)

There are NFAs of size n for which the size of the minimum sized

DFA must have size O(2 ⁿ ).

Determinisation [cont.]

NFA A ₂ : Words which end in b.

A ₂ can be determinised into the automaton DA ₂ below.

(#States = 2 ^Q .)

There are NFAs of size n for which the size of the minimum sized

DFA must have size O(2 ⁿ ).

Closure Properties

Theorem (Boolean closure)

Given NFA A ₁ , A ₂ over Σ we can construct NFA A over Σ s.t.

L(A) = L(A 1 ) (Complement). |A| = 2 ^O(|A

^|) . L(A) = L(A ₁ ) ∪ L(A ₂ ) (union). |A| = |A ₁ | + |A ₂ |.

L(A) = L(A ₁ ) ∩ L(A ₂ ) (intersection). |A| ≤ |A ₁ | · |A ₂ |.

Closure Properties

Theorem (Boolean closure)

Given NFA A ₁ , A ₂ over Σ we can construct NFA A over Σ s.t.

L(A) = L(A 1 ) (Complement). |A| = 2 ^O(|A

^|) . L(A) = L(A ₁ ) ∪ L(A ₂ ) (union). |A| = |A ₁ | + |A ₂ |.

L(A) = L(A ₁ ) ∩ L(A ₂ ) (intersection). |A| ≤ |A ₁ | · |A ₂ |.

Closure Properties

Theorem (Boolean closure)

Given NFA A ₁ , A ₂ over Σ we can construct NFA A over Σ s.t.

L(A) = L(A 1 ) (Complement). |A| = 2 ^O(|A

^|) . L(A) = L(A ₁ ) ∪ L(A ₂ ) (union). |A| = |A ₁ | + |A ₂ |.

L(A) = L(A ₁ ) ∩ L(A ₂ ) (intersection). |A| ≤ |A ₁ | · |A ₂ |.

Complementation of a NFA

A NFA A = (Q, Σ, δ, I, F ) is complemented by:

determinising it into a DFA A ⁰ = (Q ⁰ , Σ ⁰ , δ ⁰ , I ⁰ , F ⁰ ) complementing it: A ⁰ = (Q ⁰ , Σ ⁰ , δ ⁰ , I ⁰ , F ⁰ )

|A ⁰ | = |A ⁰ | = 2 ^O(|A|)

Complementation of a NFA

A NFA A = (Q, Σ, δ, I, F ) is complemented by:

determinising it into a DFA A ⁰ = (Q ⁰ , Σ ⁰ , δ ⁰ , I ⁰ , F ⁰ ) complementing it: A ⁰ = (Q ⁰ , Σ ⁰ , δ ⁰ , I ⁰ , F ⁰ )

|A ⁰ | = |A ⁰ | = 2 ^O(|A|)

Complementation of a NFA

A NFA A = (Q, Σ, δ, I, F ) is complemented by:

determinising it into a DFA A ⁰ = (Q ⁰ , Σ ⁰ , δ ⁰ , I ⁰ , F ⁰ ) complementing it: A ⁰ = (Q ⁰ , Σ ⁰ , δ ⁰ , I ⁰ , F ⁰ )

|A ⁰ | = |A ⁰ | = 2 ^O(|A|)

Complementation of a NFA

A NFA A = (Q, Σ, δ, I, F ) is complemented by:

determinising it into a DFA A ⁰ = (Q ⁰ , Σ ⁰ , δ ⁰ , I ⁰ , F ⁰ ) complementing it: A ⁰ = (Q ⁰ , Σ ⁰ , δ ⁰ , I ⁰ , F ⁰ )

|A ⁰ | = |A ⁰ | = 2 ^O(|A|)

Union of two NFAs

Definition: union of NFAs

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 ₂

Union of two NFAs

Definition: union of NFAs

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 ₂

Union of two NFAs

Definition: union of NFAs

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 ₂

Union of two NFAs

Definition: union of NFAs

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 ₂

Union of two NFAs

Definition: union of NFAs

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 ₂

Synchronous Product Construction

Definition: product of NFAs

Let A ₁ = (Q ₁ , Σ, δ ₁ , I ₁ , F ₁ ) and A ₂ = (Q ₂ , Σ, δ ₂ , I ₂ , F ₂ ).

Then, A ₁ × A ₂ = (Q, Σ, δ, I, F ) where Q = Q ₁ × Q ₂ ,

I = I ₁ × I ₂ , F = F ₁ × F 2 ,

hp, qi −→ hp ^{a 0} , q ⁰ i iff p −→ p ^{a 0} and q −→ q ^{a 0} .

Theorem

L(A ₁ × A ₂ ) = L(A ₁ ) ∩ L(A ₂ ).

|(A 1 × A 2 )| ≤ |A ₁ | · |A 2 |.

Synchronous Product Construction

Definition: product of NFAs

Let A ₁ = (Q ₁ , Σ, δ ₁ , I ₁ , F ₁ ) and A ₂ = (Q ₂ , Σ, δ ₂ , I ₂ , F ₂ ).

Then, A ₁ × A ₂ = (Q, Σ, δ, I, F ) where Q = Q ₁ × Q ₂ ,

I = I ₁ × I ₂ , F = F ₁ × F 2 ,

hp, qi −→ hp ^{a 0} , q ⁰ i iff p −→ p ^{a 0} and q −→ q ^{a 0} .

Theorem

L(A ₁ × A ₂ ) = L(A ₁ ) ∩ L(A ₂ ).

|(A 1 × A 2 )| ≤ |A ₁ | · |A 2 |.

Example

A ₁ recognizes words with an even number of b’s.

A ₂ recognizes words with a number of a’s multiple of 3.

The Product Automaton A ₁ × A 2 with F = {s ₀ , t ₀ }.

Example

A ₁ recognizes words with an even number of b’s.

A ₂ recognizes words with a number of a’s multiple of 3.

The Product Automaton A ₁ × A 2 with F = {s ₀ , t ₀ }.

Example

A ₁ recognizes words with an even number of b’s.

A ₂ recognizes words with a number of a’s multiple of 3.

The Product Automaton A ₁ × A 2 with F = {s ₀ , t ₀ }.

Example

A ₁ recognizes words with an even number of b’s.

A ₂ recognizes words with a number of a’s multiple of 3.

The Product Automaton A ₁ × A 2 with F = {s ₀ , t ₀ }.

Regular Expressions

Syntax: ∅ |  | a | reg ₁ .reg ₂ | reg ₁ |reg ₂ | reg ^∗ . Every regular expression reg denotes a language L(reg).

Example: a ^∗ .(b|bb).a ^∗ . The words with either 1 b or 2 consecutive b’s.

Theorem

For every regular expression reg we can construct a language equivalent NFA of size O(|reg|).

Theorem

For every DFA A we can construct a language equivalent regular

expression reg(A).

Regular Expressions

Syntax: ∅ |  | a | reg ₁ .reg ₂ | reg ₁ |reg ₂ | reg ^∗ . Every regular expression reg denotes a language L(reg).

Example: a ^∗ .(b|bb).a ^∗ . The words with either 1 b or 2 consecutive b’s.

Theorem

For every regular expression reg we can construct a language equivalent NFA of size O(|reg|).

Theorem

For every DFA A we can construct a language equivalent regular

expression reg(A).

Regular Expressions

Syntax: ∅ |  | a | reg ₁ .reg ₂ | reg ₁ |reg ₂ | reg ^∗ . Every regular expression reg denotes a language L(reg).

Example: a ^∗ .(b|bb).a ^∗ . The words with either 1 b or 2 consecutive b’s.

Theorem

For every regular expression reg we can construct a language equivalent NFA of size O(|reg|).

Theorem

For every DFA A we can construct a language equivalent regular

expression reg(A).

Regular Expressions

Syntax: ∅ |  | a | reg ₁ .reg ₂ | reg ₁ |reg ₂ | reg ^∗ . Every regular expression reg denotes a language L(reg).

Example: a ^∗ .(b|bb).a ^∗ . The words with either 1 b or 2 consecutive b’s.

Theorem

For every regular expression reg we can construct a language equivalent NFA of size O(|reg|).

Theorem

For every DFA A we can construct a language equivalent regular

expression reg(A).

Regular Expressions

Syntax: ∅ |  | a | reg ₁ .reg ₂ | reg ₁ |reg ₂ | reg ^∗ . Every regular expression reg denotes a language L(reg).

Example: a ^∗ .(b|bb).a ^∗ . The words with either 1 b or 2 consecutive b’s.

Theorem

For every regular expression reg we can construct a language equivalent NFA of size O(|reg|).

Theorem

For every DFA A we can construct a language equivalent regular

expression reg(A).

Outline

1 Background: Finite-Word Automata Language Containment

Automata on Finite Words

2 Infinite-Word Automata Automata on Infinite Words Emptiness Checking

3 The Automata-Theoretic Approach to Model Checking Automata-Theoretic LTL Model Checking

From Kripke Structures to Büchi Automata

From LTL Formulas to Büchi Automata: generalities On-the-fly construction of Bu¨chi Automata from LTL Complexity

4 Exercises

Outline

1 Background: Finite-Word Automata Language Containment

Automata on Finite Words

2 Infinite-Word Automata Automata on Infinite Words Emptiness Checking

3 The Automata-Theoretic Approach to Model Checking Automata-Theoretic LTL Model Checking

From Kripke Structures to Büchi Automata

From LTL Formulas to Büchi Automata: generalities On-the-fly construction of Bu¨chi Automata from LTL Complexity

4 Exercises

Infinite Word Languages

Modeling infinite computations of reactive systems.

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

Infinite Word Languages

Modeling infinite computations of reactive systems.

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

Infinite Word Languages

Modeling infinite computations of reactive systems.

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 ρ.)

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 ρ.)

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 ρ.)

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 ρ.)

Büchi Automata

Nondeterministic Büchi Automaton

A = (Q, Σ, δ, I, F ), where F ⊆ Q is the set of accepting states.

A run ρ of A on ω-word α = a ₀ , a ₁ , a ₂ , ... is an infinite sequence ρ = q _o , q ₁ , q ₂ , . . . s.t. q ₀ ∈ I and q _i −→ q ^a

_i+1 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 Automata

Nondeterministic Büchi Automaton

A = (Q, Σ, δ, I, F ), where F ⊆ Q is the set of accepting states.

A run ρ of A on ω-word α = a ₀ , a ₁ , a ₂ , ... is an infinite sequence ρ = q _o , q ₁ , q ₂ , . . . s.t. q ₀ ∈ I and q _i −→ q ^a

_i+1 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 Automata

Nondeterministic Büchi Automaton

A = (Q, Σ, δ, I, F ), where F ⊆ Q is the set of accepting states.

A run ρ of A on ω-word α = a ₀ , a ₁ , a ₂ , ... is an infinite sequence ρ = q _o , q ₁ , q ₂ , . . . s.t. q ₀ ∈ I and q _i −→ q ^a

_i+1 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 Automata

Nondeterministic Büchi Automaton

A = (Q, Σ, δ, I, F ), where F ⊆ Q is the set of accepting states.

A run ρ of A on ω-word α = a ₀ , a ₁ , a ₂ , ... is an infinite sequence ρ = q _o , q ₁ , q ₂ , . . . s.t. q ₀ ∈ I and q _i −→ q ^a

_i+1 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.

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.

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.

Büchi Automaton: Example (2)

Let a Nondeterministic Büchi Automaton (NBA) A ₂ be

With F = {s ₂ }, the automaton A 2 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 ₂

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 ₂

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 ₂

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 ₂

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 1 | · |A 2 | · 2.

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 1 | · |A 2 | · 2.

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 1 | · |A 2 | · 2.

Union of two NBAs

Definition: union of NBAs

Let A ₁ = (Q ₁ , Σ ₁ , δ ₁ , I ₁ , F ₁ ), A ₂ = (Q ₂ , Σ ₂ , δ ₂ , I ₂ , F ₂ ).

Then A = A ₁ ∪ A 2 = (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)

Union of two NBAs

Definition: union of NBAs

Let A ₁ = (Q ₁ , Σ ₁ , δ ₁ , I ₁ , F ₁ ), A ₂ = (Q ₂ , Σ ₂ , δ ₂ , I ₂ , F ₂ ).

Then A = A ₁ ∪ A 2 = (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)

Union of two NBAs

Definition: union of NBAs

Let A ₁ = (Q ₁ , Σ ₁ , δ ₁ , I ₁ , F ₁ ), A ₂ = (Q ₂ , Σ ₂ , δ ₂ , I ₂ , F ₂ ).

Then A = A ₁ ∪ A 2 = (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)

Union of two NBAs

Definition: union of NBAs

Let A ₁ = (Q ₁ , Σ ₁ , δ ₁ , I ₁ , F ₁ ), A ₂ = (Q ₂ , Σ ₂ , δ ₂ , I ₂ , F ₂ ).

Then A = A ₁ ∪ A 2 = (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)

Union of two NBAs

Definition: union of NBAs

Let A ₁ = (Q ₁ , Σ ₁ , δ ₁ , I ₁ , F ₁ ), A ₂ = (Q ₂ , Σ ₂ , δ ₂ , I ₂ , F ₂ ).

Then A = A ₁ ∪ A 2 = (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)

Synchronous Product of NBAs

Definition: synchronous product of NBAs

Let A ₁ = (Q ₁ , Σ, δ ₁ , I ₁ , F ₁ ) and A ₂ = (Q ₂ , Σ, δ ₂ , I ₂ , F ₂ ).

Then, A ₁ × A 2 = (Q, Σ, δ, I, F ), where Q = Q ₁ × Q 2 × {1, 2}.

I = I ₁ × I ₂ × {1}.

F = F ₁ × Q ₂ × {1}.

hp, q, 1i −→ hp ^{a 0} , q ⁰ , 1i iff p −→ p ^{a 0} and q −→ q ^{a 0} and p 6∈ F ₁ . hp, q, 1i −→ hp ^{a 0} , q ⁰ , 2i iff p −→ p ^{a 0} and q −→ q ^{a 0} and p ∈ F ₁ . hp, q, 2i −→ hp ^{a 0} , q ⁰ , 2i iff p −→ p ^{a 0} and q −→ q ^{a 0} and q 6∈ F ₂ . hp, q, 2i −→ hp ^{a 0} , q ⁰ , 1i iff p −→ p ^{a 0} and q −→ q ^{a 0} and q ∈ F ₂ . Theorem

L(A ₁ × A ₂ ) = L(A ₁ ) ∩ L(A ₂ ).

|A ₁ × A ₂ | ≤ 2 · |A ₁ | · |A ₂ |.

Synchronous Product of NBAs

Definition: synchronous product of NBAs

Let A ₁ = (Q ₁ , Σ, δ ₁ , I ₁ , F ₁ ) and A ₂ = (Q ₂ , Σ, δ ₂ , I ₂ , F ₂ ).

Then, A ₁ × A 2 = (Q, Σ, δ, I, F ), where Q = Q ₁ × Q 2 × {1, 2}.

I = I ₁ × I ₂ × {1}.

F = F ₁ × Q ₂ × {1}.

hp, q, 1i −→ hp ^{a 0} , q ⁰ , 1i iff p −→ p ^{a 0} and q −→ q ^{a 0} and p 6∈ F ₁ . hp, q, 1i −→ hp ^{a 0} , q ⁰ , 2i iff p −→ p ^{a 0} and q −→ q ^{a 0} and p ∈ F ₁ . hp, q, 2i −→ hp ^{a 0} , q ⁰ , 2i iff p −→ p ^{a 0} and q −→ q ^{a 0} and q 6∈ F ₂ . hp, q, 2i −→ hp ^{a 0} , q ⁰ , 1i iff p −→ p ^{a 0} and q −→ q ^{a 0} and q ∈ F ₂ . Theorem

L(A ₁ × A ₂ ) = L(A ₁ ) ∩ L(A ₂ ).

|A ₁ × A ₂ | ≤ 2 · |A ₁ | · |A ₂ |.

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 2 .

I = I ₁ × I ₂ .

F = F ₁ × Q ₂ .

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 2 .

I = I ₁ × I ₂ .

F = F ₁ × Q ₂ .

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 2 .

I = I ₁ × I ₂ .

F = F ₁ × Q ₂ .

Product of NBAs: Example

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 ^|A

^|·log(|A

^|) ).

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.

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 ^|A

^|·log(|A

^|) ).

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.

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 ^|A

^|·log(|A

^|) ).

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.

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 ^|A

^|·log(|A

^|) ).

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.

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 ^|A

^|·log(|A

^|) ).

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.

Generalized Büchi Automaton

Definition

A Generalized Büchi Automaton is a tuple A := (Q, Σ, δ, I, FT ) where FT = hF ₁ , F ₂ , . . . , F _k i with F _i ⊆ Q.

A run ρ of A is accepting if Inf (ρ) ∩ F _i 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 _i . Then, it

moves to (i + 1)mod K mode.

Generalized Büchi Automaton

Definition

A Generalized Büchi Automaton is a tuple A := (Q, Σ, δ, I, FT ) where FT = hF ₁ , F ₂ , . . . , F _k i with F _i ⊆ Q.

A run ρ of A is accepting if Inf (ρ) ∩ F _i 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 _i . Then, it

moves to (i + 1)mod K mode.

Generalized Büchi Automaton

Definition

A Generalized Büchi Automaton is a tuple A := (Q, Σ, δ, I, FT ) where FT = hF ₁ , F ₂ , . . . , F _k i with F _i ⊆ Q.

A run ρ of A is accepting if Inf (ρ) ∩ F _i 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 _i . Then, it

moves to (i + 1)mod K mode.