THE SYNTHESIS PROBLEM

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

The Synthesis Problem

Angelo Montanari

Dept. of Mathematics, Computer Science, and Physics University of Udine, Italy

First Summer School on

Formal Methods for Cyber-Physical Systems Verona, 12-13 September, 2017

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

1. THE SYNTHESIS PROBLEM

Introduction to the synthesis problem The solution schema

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

W

As a matter of fact, the expression “synthesis problem” has been used to designate quite different problems.

As an example, sometimes the synthesis problem is identified with the model building problem, that is, the problem of providing an

algorithm that, given a formula of the logic under consideration, produces a complete description of a specific model of it, whenever it is satisfiable.

See, for instance, French, McCabe-Dansted, and Reynolds, Synthesis for continuous time, Theoretical Computer Science, 594: 201-222, 2015. Here, we refer to theoriginal formulationof thesynthesis problem given by Church and to the solution provided by B ¨uchi and Landweber.

Our presentation of the problem and of the solution follow the tutorial:

“Solution of Church’s Problem: A Tutorial”, by Wolfgang Thomas.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

W

As a matter of fact, the expression “synthesis problem” has been used to designate quite different problems.

As an example, sometimes the synthesis problem is identified with the model building problem, that is, the problem of providing an

algorithm that, given a formula of the logic under consideration, produces a complete description of a specific model of it, whenever it is satisfiable.

See, for instance, French, McCabe-Dansted, and Reynolds, Synthesis for continuous time, Theoretical Computer Science, 594: 201-222, 2015.

Here, we refer to theoriginal formulationof thesynthesis problem given by Church and to the solution provided by B ¨uchi and Landweber.

Our presentation of the problem and of the solution follow the tutorial:

“Solution of Church’s Problem: A Tutorial”, by Wolfgang Thomas.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

W

As a matter of fact, the expression “synthesis problem” has been used to designate quite different problems.

As an example, sometimes the synthesis problem is identified with the model building problem, that is, the problem of providing an

algorithm that, given a formula of the logic under consideration, produces a complete description of a specific model of it, whenever it is satisfiable.

See, for instance, French, McCabe-Dansted, and Reynolds, Synthesis for continuous time, Theoretical Computer Science, 594: 201-222, 2015.

Here, we refer to theoriginal formulationof thesynthesis problem given by Church and to the solution provided by B ¨uchi and Landweber.

Our presentation of the problem and of the solution follow the tutorial:

“Solution of Church’s Problem: A Tutorial”, by Wolfgang Thomas.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

W

As a matter of fact, the expression “synthesis problem” has been used to designate quite different problems.

As an example, sometimes the synthesis problem is identified with the model building problem, that is, the problem of providing an

algorithm that, given a formula of the logic under consideration, produces a complete description of a specific model of it, whenever it is satisfiable.

See, for instance, French, McCabe-Dansted, and Reynolds, Synthesis for continuous time, Theoretical Computer Science, 594: 201-222, 2015.

Here, we refer to theoriginal formulationof thesynthesis problem given by Church and to the solution provided by B ¨uchi and Landweber.

Our presentation of the problem and of the solution follow the tutorial:

“Solution of Church’s Problem: A Tutorial”, by Wolfgang Thomas.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

C

’

I Thesynthesis problemwas originally proposed by Church during the “Summer Institute of Symbolic Logic” on 1957.

I It consists of the synthesis of afinite state machine(a circuit) which realizes a bit-to-bit transformation of an infinite sequence α into a corresponding infinite sequence β so that the pair (α, β) satisfies a specification expressed in a suitable (temporal) logic.

I Goal: given a specification of the input-output relation between α e β, build a corresponding machine:

?

α=0101... β=1010...

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

C

’

I Thesynthesis problemwas originally proposed by Church during the “Summer Institute of Symbolic Logic” on 1957.

I It consists of the synthesis of afinite state machine(a circuit) which realizes a bit-to-bit transformation of an infinite sequence α into a corresponding infinite sequence β so that the pair (α, β) satisfies a specification expressed in a suitable (temporal) logic.

I Goal: given a specification of the input-output relation between α e β, build a corresponding machine:

?

α=0101... β=1010...

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

C

’

I Thesynthesis problemwas originally proposed by Church during the “Summer Institute of Symbolic Logic” on 1957.

I It consists of the synthesis of afinite state machine(a circuit) which realizes a bit-to-bit transformation of an infinite sequence α into a corresponding infinite sequence β so that the pair (α, β) satisfies a specification expressed in a suitable (temporal) logic.

I Goal: given a specification of the input-output relation between α e β, build a corresponding machine:

?

α=0101... β=1010...

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

T

B ¨

L

I The problem consists in properly filling in the black box on the basis of the specification of the relationships between the input α and the output β.

I With respect to traditional (terminating) data manipulation programs, the focus switches from data with an infinite domain, which, in general, makes the synthesis problem undecidable, to infinite time.

I Surprisingly, B ¨uchi and Landweber have shown thatChurch’s problem admits a positive solution, that is, it is decidable, provided that the specification language (the temporal logic) is not too expressive.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

T

B ¨

L

I The problem consists in properly filling in the black box on the basis of the specification of the relationships between the input α and the output β.

I With respect to traditional (terminating) data manipulation programs, the focus switches from data with an infinite domain, which, in general, makes the synthesis problem undecidable, to infinite time.

I Surprisingly, B ¨uchi and Landweber have shown thatChurch’s problem admits a positive solution, that is, it is decidable, provided that the specification language (the temporal logic) is not too expressive.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

T

B ¨

L

I The problem consists in properly filling in the black box on the basis of the specification of the relationships between the input α and the output β.

I With respect to traditional (terminating) data manipulation programs, the focus switches from data with an infinite domain, which, in general, makes the synthesis problem undecidable, to infinite time.

I Surprisingly, B ¨uchi and Landweber have shown thatChurch’s problem admits a positive solution, that is, it is decidable, provided that the specification language (the temporal logic) is not too expressive.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

A

I ∀t(α(t) = 1 → β(t) = 1)

I if, at a given time t, the input is 1, then the output is 1 as well;

I ¬∃t β(t) = β(t + 1) = 0

I there are no two consecutive occurrences of 0 in the output sequence;

I ∃^ωt α(t) = 0→ ∃^ωt β(t) = 0

I if the input sequence features an infinite number of occurrences of 0, then the output sequence features an infinite number of

occurrences of 0 as well. A solution procedure:

I if the input is 1, it produces the output 1;

I if the input is 0, it produces the output 1 if the previous output, on the input 0, was 0; otherwise, it produces the output 0.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

A

I ∀t(α(t) = 1 → β(t) = 1)

I if, at a given time t, the input is 1, then the output is 1 as well;

I ¬∃t β(t) = β(t + 1) = 0

I there are no two consecutive occurrences of 0 in the output sequence;

I ∃^ωt α(t) = 0→ ∃^ωt β(t) = 0

I if the input sequence features an infinite number of occurrences of 0, then the output sequence features an infinite number of

occurrences of 0 as well. A solution procedure:

I if the input is 1, it produces the output 1;

I if the input is 0, it produces the output 1 if the previous output, on the input 0, was 0; otherwise, it produces the output 0.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

A

I ∀t(α(t) = 1 → β(t) = 1)

I if, at a given time t, the input is 1, then the output is 1 as well;

I ¬∃t β(t) = β(t + 1) = 0

I there are no two consecutive occurrences of 0 in the output sequence;

I ∃^ωt α(t) = 0→ ∃^ωt β(t) = 0

I if the input sequence features an infinite number of occurrences of 0, then the output sequence features an infinite number of

occurrences of 0 as well.

A solution procedure:

I if the input is 1, it produces the output 1;

I if the input is 0, it produces the output 1 if the previous output, on the input 0, was 0; otherwise, it produces the output 0.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

A

I ∀t(α(t) = 1 → β(t) = 1)

I if, at a given time t, the input is 1, then the output is 1 as well;

I ¬∃t β(t) = β(t + 1) = 0

I there are no two consecutive occurrences of 0 in the output sequence;

I ∃^ωt α(t) = 0→ ∃^ωt β(t) = 0

I if the input sequence features an infinite number of occurrences of 0, then the output sequence features an infinite number of

occurrences of 0 as well.

A solution procedure:

I if the input is 1, it produces the output 1;

I if the input is 0, it produces the output 1 if the previous output, on the input 0, was 0; otherwise, it produces the output 0.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

CONDITIONS ON TRANSFORMATIONS

Thetransformationwe are looking for must satisfy the following conditions:

1. bit-to-bit- when the machine receives the n-th character of α (as input), it must immediately produce the n-th character of β (as output). It follows that β(n) may only depend on α(1), . . . , α(n− 1), α(n);

2. a finite state solution (machine)- to compute the output of a generic computation step (the output at time t), the machine needs to exploit a finite memory of a given size.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

CONDITIONS ON TRANSFORMATIONS

Thetransformationwe are looking for must satisfy the following conditions:

1. bit-to-bit- when the machine receives the n-th character of α (as input), it must immediately produce the n-th character of β (as output). It follows that β(n) may only depend on α(1), . . . , α(n− 1), α(n);

2. a finite state solution (machine)- to compute the output of a generic computation step (the output at time t), the machine needs to exploit a finite memory of a given size.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

CONDITIONS ON TRANSFORMATIONS

Thetransformationwe are looking for must satisfy the following conditions:

1. bit-to-bit- when the machine receives the n-th character of α (as input), it must immediately produce the n-th character of β (as output). It follows that β(n) may only depend on α(1), . . . , α(n− 1), α(n);

2. a finite state solution (machine)- to compute the output of a generic computation step (the output at time t), the machine needs to exploit a finite memory of a given size.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

EXAMPLES

I β(t) = α(2t)(β returns the elements at even positions of α) violates condition 1 – the output symbol β(t) must be produced without delay after receipt of the input symbol α(t);

I β(2t) = β(2t + 1) = α(t)(β “doubles” the position of each symbol of α) violates condition 2 – we need to record an unboundedly increasing number of symbols for future use;

I β = 111 . . ., if α features an infinite number of occurrences of 1; otherwise, β = 000 . . .violates condition 1 as well – the first symbol of the output sequence β cannot be determined on the basis of any finite prefix of α.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

EXAMPLES

I β(t) = α(2t)(β returns the elements at even positions of α) violates condition 1 – the output symbol β(t) must be produced without delay after receipt of the input symbol α(t);

I β(2t) = β(2t + 1) = α(t)(β “doubles” the position of each symbol of α) violates condition 2 – we need to record an unboundedly increasing number of symbols for future use;

I β = 111 . . ., if α features an infinite number of occurrences of 1; otherwise, β = 000 . . .violates condition 1 as well – the first symbol of the output sequence β cannot be determined on the basis of any finite prefix of α.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

EXAMPLES

I β(t) = α(2t)(β returns the elements at even positions of α) violates condition 1 – the output symbol β(t) must be produced without delay after receipt of the input symbol α(t);

I β(2t) = β(2t + 1) = α(t)(β “doubles” the position of each symbol of α) violates condition 2 – we need to record an unboundedly increasing number of symbols for future use;

I β = 111 . . ., if α features an infinite number of occurrences of 1;

otherwise, β = 000 . . .violates condition 1 as well – the first symbol of the output sequence β cannot be determined on the basis of any finite prefix of α.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

AFINITE STATE MACHINE

I AMealy automaton(input-output automaton or transducer)M: a finite state automaton with an output function τ : S× Σ → Γ, where S is a finite set of states, Σ is a finite input alphabet, and Γ is a finite output alphabet.

I Given an input sequence

α = α(1)α(2)· · · , the output sequence computed byM is

M(α) = β = β(1)β(2) · · · , where β(t) = τ (δ^∗(s₀, α(0)· · · α(t − 1)), α(t)) (δ^∗ extends the transition function as follows:

δ^∗(s, ) = s; δ^∗(s, wa) = δ(δ^∗(s, w), a), for w∈ Σ^∗and a∈ Σ).

I Itsatisfiesthe conditions on transformations.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

AFINITE STATE MACHINE

I AMealy automaton(input-output automaton or transducer)M: a finite state automaton with an output function τ : S× Σ → Γ, where S is a finite set of states, Σ is a finite input alphabet, and Γ is a finite output alphabet.

I Given an input sequence

α = α(1)α(2)· · · , the output sequence computed byM is

M(α) = β = β(1)β(2) · · · , where β(t) = τ (δ^∗(s₀, α(0)· · · α(t − 1)), α(t)) (δ^∗ extends the transition function as follows:

δ^∗(s, ) = s; δ^∗(s, wa) = δ(δ^∗(s, w), a), for w∈ Σ^∗and a∈ Σ).

I Itsatisfiesthe conditions on transformations.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

AFINITE STATE MACHINE

I AMealy automaton(input-output automaton or transducer)M: a finite state automaton with an output function τ : S× Σ → Γ, where S is a finite set of states, Σ is a finite input alphabet, and Γ is a finite output alphabet.

I Given an input sequence

α = α(1)α(2)· · · , the output sequence computed byM is

M(α) = β = β(1)β(2) · · · , where β(t) = τ (δ^∗(s₀, α(0)· · · α(t − 1)), α(t)) (δ^∗ extends the transition function as follows:

δ^∗(s, ) = s; δ^∗(s, wa) = δ(δ^∗(s, w), a), for w∈ Σ^∗and a∈ Σ).

I Itsatisfiesthe conditions on transformations.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

THE SPECIFICATION LANGUAGE

I S1S: the monadic second-order logic of one successordenoted by (ω, +1).

I The ordering relation < is (second-order) definable in terms of the successor function +1: s < t if and only if t belongs to each set that includes s + 1 and is closed under successor.

I For the sake of simplicity, we will only consider Boolean input and output alphabets, that is,{0, 1}.

I The S1S-formulas ϕ(X, Y) we will take into consideration talk about sequences α∈ {0, 1}^ω and β∈ {0, 1}^ω.

The free variable X identifies those positions where α takes value 1, while the free variable Y identifies those where β takes value 1. We denote the interpretations of X and Y induced by α and β by Pαand Pβ, respectively.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

THE SPECIFICATION LANGUAGE

I S1S: the monadic second-order logic of one successordenoted by (ω, +1).

I The ordering relation < is (second-order) definable in terms of the successor function +1: s < t if and only if t belongs to each set that includes s + 1 and is closed under successor.

I For the sake of simplicity, we will only consider Boolean input and output alphabets, that is,{0, 1}.

I The S1S-formulas ϕ(X, Y) we will take into consideration talk about sequences α∈ {0, 1}^ω and β∈ {0, 1}^ω.

The free variable X identifies those positions where α takes value 1, while the free variable Y identifies those where β takes value 1. We denote the interpretations of X and Y induced by α and β by Pαand Pβ, respectively.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

THE SPECIFICATION LANGUAGE

I S1S: the monadic second-order logic of one successordenoted by (ω, +1).

I The ordering relation < is (second-order) definable in terms of the successor function +1: s < t if and only if t belongs to each set that includes s + 1 and is closed under successor.

I For the sake of simplicity, we will only consider Boolean input and output alphabets, that is,{0, 1}.

I The S1S-formulas ϕ(X, Y) we will take into consideration talk about sequences α∈ {0, 1}^ω and β∈ {0, 1}^ω.

The free variable X identifies those positions where α takes value 1, while the free variable Y identifies those where β takes value 1. We denote the interpretations of X and Y induced by α and β by Pαand Pβ, respectively.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

THE SPECIFICATION LANGUAGE

I S1S: the monadic second-order logic of one successordenoted by (ω, +1).

I The ordering relation < is (second-order) definable in terms of the successor function +1: s < t if and only if t belongs to each set that includes s + 1 and is closed under successor.

I For the sake of simplicity, we will only consider Boolean input and output alphabets, that is,{0, 1}.

I The S1S-formulas ϕ(X, Y) we will take into consideration talk about sequences α∈ {0, 1}^ω and β∈ {0, 1}^ω.

The free variable X identifies those positions where α takes value 1, while the free variable Y identifies those where β takes value 1.

We denote the interpretations of X and Y induced by α and β by Pαand Pβ, respectively.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

CHURCH’S PROBLEM

Church’s problemcan be precisely stated as follows:

given an S1S-formula ϕ(X, Y), build a Mealy automatonM, with input alphabet Σ ={0, 1} and output alphabet Γ = {0, 1}, such that, for every input sequence α∈ {0, 1}^ω,M generates an output sequence β ∈ {0, 1}^ω such that (ω, +1) ϕ[P^α, Pβ] (or it answers that such an automaton does not exist).

It can be easily generalized to an input alphabet Σ ={0, 1}^m1 and/or to an output alphabet Γ ={0, 1}^m2.

Afinite state winning strategy for an infinite game: according to a game-theoretic interpretation, a Mealy automaton can be viewed as the definition of awinning strategyfor player B/β (Bob) that replies to the moves of player A/α (Alice).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

CHURCH’S PROBLEM

Church’s problemcan be precisely stated as follows:

given an S1S-formula ϕ(X, Y), build a Mealy automatonM, with input alphabet Σ ={0, 1} and output alphabet Γ = {0, 1}, such that, for every input sequence α∈ {0, 1}^ω,M generates an output sequence β ∈ {0, 1}^ω such that (ω, +1) ϕ[P^α, Pβ] (or it answers that such an automaton does not exist).

It can be easily generalized to an input alphabet Σ ={0, 1}^m1 and/or to an output alphabet Γ ={0, 1}^m2.

Afinite state winning strategy for an infinite game: according to a game-theoretic interpretation, a Mealy automaton can be viewed as the definition of awinning strategyfor player B/β (Bob) that replies to the moves of player A/α (Alice).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(

’

)

CHURCH’S PROBLEM

Church’s problemcan be precisely stated as follows:

given an S1S-formula ϕ(X, Y), build a Mealy automatonM, with input alphabet Σ ={0, 1} and output alphabet Γ = {0, 1}, such that, for every input sequence α∈ {0, 1}^ω,M generates an output sequence β ∈ {0, 1}^ω such that (ω, +1) ϕ[P^α, Pβ] (or it answers that such an automaton does not exist).

It can be easily generalized to an input alphabet Σ ={0, 1}^m1 and/or to an output alphabet Γ ={0, 1}^m2.

Afinite state winning strategy for an infinite game: according to a game-theoretic interpretation, a Mealy automaton can be viewed as the definition of awinning strategyfor player B/β (Bob) that replies to the moves of player A/α (Alice).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

T

B ¨

-L

I Thesolution by B ¨uchi-Landweberis based on a series of

transformations that, starting from thelogical characterization of the problem, allow one to first replace it with a characterization based onautomataon infinite words (Muller automata) and then with a characterization based on infinitegames(which are played on the transition graph of the automaton).

S1S

⇓

(Deterministic) Muller automata

⇓ Muller games

⇓ Parity games

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

T

B ¨

-L

I Thesolution by B ¨uchi-Landweberis based on a series of

transformations that, starting from thelogical characterization of the problem, allow one to first replace it with a characterization based onautomataon infinite words (Muller automata) and then with a characterization based on infinitegames(which are played on the transition graph of the automaton).

S1S

⇓

(Deterministic) Muller automata

⇓ Muller games

⇓ Parity games

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(M

)

I We first transform anS1S specificationϕ(X, Y) into adeterministic Muller automatonA, that recognizes infinite words γ in

({0, 1} × {0, 1})^ω, in such a way that

I A accepts γ if and only if (ω, +1)  ϕ[P^γ].

I From automata theory, we know that:

(i) S1S formulas are equivalent to nondeterministic B ¨uchi

automata (NBA) and NBA are equivalent to deterministic Muller automata (DMA);

(ii) these transformations are effective.

I Muller acceptance condition: given a collection of sets of states F = {F¹, ..., Fk}, a computation σ is accepted by A if the set of states that occur infinitely often in σ belongs toF.

I Remark: the above transformations arecomputable but extremely expensive(in terms of resources), as|Aϕ| cannot be bounded by a function elementary in the size of|ϕ|.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(M

)

I We first transform anS1S specificationϕ(X, Y) into adeterministic Muller automatonA, that recognizes infinite words γ in

({0, 1} × {0, 1})^ω, in such a way that

I A accepts γ if and only if (ω, +1)  ϕ[P^γ].

I From automata theory, we know that:

(i) S1S formulas are equivalent to nondeterministic B ¨uchi

automata (NBA) and NBA are equivalent to deterministic Muller automata (DMA);

(ii) these transformations are effective.

I Muller acceptance condition: given a collection of sets of states F = {F¹, ..., Fk}, a computation σ is accepted by A if the set of states that occur infinitely often in σ belongs toF.

I Remark: the above transformations arecomputable but extremely expensive(in terms of resources), as|Aϕ| cannot be bounded by a function elementary in the size of|ϕ|.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(M

)

I We first transform anS1S specificationϕ(X, Y) into adeterministic Muller automatonA, that recognizes infinite words γ in

({0, 1} × {0, 1})^ω, in such a way that

I A accepts γ if and only if (ω, +1)  ϕ[P^γ].

I From automata theory, we know that:

(i) S1S formulas are equivalent to nondeterministic B ¨uchi

automata (NBA) and NBA are equivalent to deterministic Muller automata (DMA);

(ii) these transformations are effective.

I Muller acceptance condition: given a collection of sets of states F = {F¹, ..., Fk}, a computation σ is accepted by A if the set of states that occur infinitely often in σ belongs toF.

I Remark: the above transformations arecomputable but extremely expensive(in terms of resources), as|A^ϕ| cannot be bounded by a function elementary in the size of|ϕ|.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(M

)

(M

)

I Theautomatonat the previous step is then transformed into the graph of atwo player game.

I Such a transformation allows one to make the contributions (in terms of bits) of the two players explicit.

Church’s Problem 7

as initial state. From each state we have, for each bit pair (b1, b2), a transi- tion labelled (b1, b2) to the state (b1, b2). A set F is accepting if it satisfies the following condition: If the first component is 0 in some state of F , then the second component is 0 for some (possibly different) state of F .

It is known how to combine Muller automata for several conditions to a single Muller automaton for their conjunction. We do not present it explicitly here for our example. Rather we turn to a variant, called “finite- state game with Muller winning condition”. This approach, introduced by McNaughton [11], is motivated by the view that the two components of an input letter of the Muller automaton are contributed by two players A and B who pursue antagonistic objectives: A aims at violating the condition ϕ and B at satisfying it.

2.2 From Automata to Games

We distinguish the contribution of bits (in the general case: bit vectors) by two players A and B by introducing two kinds of states, called A- and B-states. In an A-state, the next bit is to be picked by player A, in a B-state by player B. We indicate A-states by boxes and B-states by circles. The figure below indicates how we dissolve transitions from a state in the given Muller automaton by introducing intermediate states and corresponding transitions.

•

• • • •

!0 0

"

!0 1

" !1 0

"

!1 1

"

!

0 1

0 1 0 1

Note that we keep every state of the Muller automaton as an A-state. For each A-state q and bit b, we introduce a b-labelled transition to a new state called (q, b), and from (q, b) for each bit c a c-labelled transition to the state p which was reached from q by!b

c

"

in the original automaton. For such a state p we call c the corresponding “output bit”, denoted out(q, b, p). (If both c- transitions from (q, b) lead to the same state p we agree that out(q, b, p) = 0.) If the input alphabet is {0, 1}^m1 and the output alphabet {0, 1}^m2, we introduce B-states (q, b) with b∈ {0, 1}^m1, and define out(q, b, p) as a vector in {0, 1}^m2.

The result is a “game graph”. For our example specification above, we can obtain the following game graph from a corresponding Muller automa- ton (the reader should ignore for the moment the boldface notation of some arrows).

I  = states of A (states of the Muller automaton)

I = states of B

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(M

)

(M

)

I Theautomatonat the previous step is then transformed into the graph of atwo player game.

I Such a transformation allows one to make the contributions (in terms of bits) of the two players explicit.

Church’s Problem 7

as initial state. From each state we have, for each bit pair (b1, b2), a transi- tion labelled (b1, b2) to the state (b1, b2). A set F is accepting if it satisfies the following condition: If the first component is 0 in some state of F , then the second component is 0 for some (possibly different) state of F .

It is known how to combine Muller automata for several conditions to a single Muller automaton for their conjunction. We do not present it explicitly here for our example. Rather we turn to a variant, called “finite- state game with Muller winning condition”. This approach, introduced by McNaughton [11], is motivated by the view that the two components of an input letter of the Muller automaton are contributed by two players A and B who pursue antagonistic objectives: A aims at violating the condition ϕ and B at satisfying it.

2.2 From Automata to Games

We distinguish the contribution of bits (in the general case: bit vectors) by two players A and B by introducing two kinds of states, called A- and B-states. In an A-state, the next bit is to be picked by player A, in a B-state by player B. We indicate A-states by boxes and B-states by circles. The figure below indicates how we dissolve transitions from a state in the given Muller automaton by introducing intermediate states and corresponding transitions.

•

• • • •

!0 0

"

!0 1

" !1 0

"

!1 1

"

!

0 1

0 1 0 1

Note that we keep every state of the Muller automaton as an A-state. For each A-state q and bit b, we introduce a b-labelled transition to a new state called (q, b), and from (q, b) for each bit c a c-labelled transition to the state p which was reached from q by!b

c

"

in the original automaton. For such a state p we call c the corresponding “output bit”, denoted out(q, b, p). (If both c- transitions from (q, b) lead to the same state p we agree that out(q, b, p) = 0.) If the input alphabet is {0, 1}^m1 and the output alphabet {0, 1}^m2, we introduce B-states (q, b) with b∈ {0, 1}^m1, and define out(q, b, p) as a vector in {0, 1}^m2.

The result is a “game graph”. For our example specification above, we can obtain the following game graph from a corresponding Muller automa- ton (the reader should ignore for the moment the boldface notation of some arrows).

I  = states of A (states of the Muller automaton)

I = states of B

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

F

(M

)

(M

)

I Theautomatonat the previous step is then transformed into the graph of atwo player game.

I Such a transformation allows one to make the contributions (in terms of bits) of the two players explicit.

Church’s Problem 7

as initial state. From each state we have, for each bit pair (b1, b2), a transi- tion labelled (b1, b2) to the state (b1, b2). A set F is accepting if it satisfies the following condition: If the first component is 0 in some state of F , then the second component is 0 for some (possibly different) state of F .

It is known how to combine Muller automata for several conditions to a single Muller automaton for their conjunction. We do not present it explicitly here for our example. Rather we turn to a variant, called “finite- state game with Muller winning condition”. This approach, introduced by McNaughton [11], is motivated by the view that the two components of an input letter of the Muller automaton are contributed by two players A and B who pursue antagonistic objectives: A aims at violating the condition ϕ and B at satisfying it.

2.2 From Automata to Games

We distinguish the contribution of bits (in the general case: bit vectors) by two players A and B by introducing two kinds of states, called A- and B-states. In an A-state, the next bit is to be picked by player A, in a B-state by player B. We indicate A-states by boxes and B-states by circles. The figure below indicates how we dissolve transitions from a state in the given Muller automaton by introducing intermediate states and corresponding transitions.

•

• • • •

!0 0

"

!0 1

" !1 0

"

!1 1

"

!

0 1

0 1 0 1

Note that we keep every state of the Muller automaton as an A-state. For each A-state q and bit b, we introduce a b-labelled transition to a new state called (q, b), and from (q, b) for each bit c a c-labelled transition to the state p which was reached from q by!b

c

"

in the original automaton. For such a state p we call c the corresponding “output bit”, denoted out(q, b, p). (If both c- transitions from (q, b) lead to the same state p we agree that out(q, b, p) = 0.) If the input alphabet is {0, 1}^m1 and the output alphabet {0, 1}^m2, we introduce B-states (q, b) with b∈ {0, 1}^m1, and define out(q, b, p) as a vector in {0, 1}^m2.

The result is a “game graph”. For our example specification above, we can obtain the following game graph from a corresponding Muller automa- ton (the reader should ignore for the moment the boldface notation of some

I  = states of A (states of the Muller automaton)

I = states of B

Angelo Montanari The Synthesis Problem September 14, 2017 14 / 40

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

N

I For each A-state q and each bit b, we introduce a transition labeled by b to a new B-state that we call (q, b).

I For each bit c, we introduce a transition labeled by c from the B-state (q, b) to the A-state p whenever in the original Muller automaton it is possible to move from q to p via a transition labeled by the pair of bits (b, c).

I For such a state p, we define c as the output bit and we denote it by out(q, b, p) (if both transitions exiting from (q, b) lead to the same state p, we put by convention out(q, b, p) = 0).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

N

I For each A-state q and each bit b, we introduce a transition labeled by b to a new B-state that we call (q, b).

I For each bit c, we introduce a transition labeled by c from the B-state (q, b) to the A-state p whenever in the original Muller automaton it is possible to move from q to p via a transition labeled by the pair of bits (b, c).

I For such a state p, we define c as the output bit and we denote it by out(q, b, p) (if both transitions exiting from (q, b) lead to the same state p, we put by convention out(q, b, p) = 0).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

N

I For each A-state q and each bit b, we introduce a transition labeled by b to a new B-state that we call (q, b).

I For each bit c, we introduce a transition labeled by c from the B-state (q, b) to the A-state p whenever in the original Muller automaton it is possible to move from q to p via a transition labeled by the pair of bits (b, c).

I For such a state p, we define c as the output bit and we denote it by out(q, b, p) (if both transitions exiting from (q, b) lead to the same state p, we put by convention out(q, b, p) = 0).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

S

Some effects of the replacement of automata by games.

I The game-theoretic perspective introducesa symmetry between input and output: player A, who provides the input, aims at falsifying the specification; player B, who provides the output, aims at satisfying it. As we will see, it is possible to prove that one of the two players has a winning strategy (a feature which was hidden in the original formulation of the problem).

I The game-theoretic perspectivedoes not assign a special role to the initial state: the problem is to determine for each state which player has a winning strategy in a game that starts from such a state.

I The labels associated with the transitions can beinitially ignored, as the winning conditions are given in terms of visited states, and only subsequently reintroduced, when the Mealy automaton must be synthesized.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

S

Some effects of the replacement of automata by games.

I The game-theoretic perspective introducesa symmetry between input and output: player A, who provides the input, aims at falsifying the specification; player B, who provides the output, aims at satisfying it. As we will see, it is possible to prove that one of the two players has a winning strategy (a feature which was hidden in the original formulation of the problem).

I The game-theoretic perspectivedoes not assign a special role to the initial state: the problem is to determine for each state which player has a winning strategy in a game that starts from such a state.

I The labels associated with the transitions can beinitially ignored, as the winning conditions are given in terms of visited states, and only subsequently reintroduced, when the Mealy automaton must be synthesized.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

S

Some effects of the replacement of automata by games.

I The game-theoretic perspective introducesa symmetry between input and output: player A, who provides the input, aims at falsifying the specification; player B, who provides the output, aims at satisfying it. As we will see, it is possible to prove that one of the two players has a winning strategy (a feature which was hidden in the original formulation of the problem).

I The game-theoretic perspectivedoes not assign a special role to the initial state: the problem is to determine for each state which player has a winning strategy in a game that starts from such a state.

I The labels associated with the transitions can beinitially ignored, as the winning conditions are given in terms of visited states, and only subsequently reintroduced, when the Mealy automaton must be synthesized.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

S

Some effects of the replacement of automata by games.

I The game-theoretic perspective introducesa symmetry between input and output: player A, who provides the input, aims at falsifying the specification; player B, who provides the output, aims at satisfying it. As we will see, it is possible to prove that one of the two players has a winning strategy (a feature which was hidden in the original formulation of the problem).

I The game-theoretic perspectivedoes not assign a special role to the initial state: the problem is to determine for each state which player has a winning strategy in a game that starts from such a state.

I The labels associated with the transitions can beinitially ignored, as the winning conditions are given in terms of visited states, and only subsequently reintroduced, when the Mealy automaton must be synthesized.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

G

M

An important remark.

Do not confusethe states of the game graph with the states of the (finite state) Mealy automaton: the Mealy automaton works on the game graph, but its states are not the states of the game graph.

As we will see, to solve Church’s problem we need tocombinein suitable way the states of the Mealy automaton and those of the game graph.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

T

In the following, we show how to obtain a solution to Church’s problem in two steps, starting from a finite game graph with Muller winning conditions:

1. to establish whether or not B wins;

2. in case of a positive answer, to provide a (finite state) winning strategy.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

2. INFINITE GAMES AND B ¨UCHI-LANDWEBER THEOREM

Infinite games

B ¨uchi-Landweber Theorem

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

I

I Thegame graph(arena) is a graph G = (Q, Q_A, E), with Q_A⊆ Q and E⊆ Q × Q, where ∀q ∈ Q : qE 6= ∅ (no deadlock). Let Q_B= Q\ QA. We will only consider finite game graphs.

Moreover, by construction, each edge leads from a state in QAto a state in Q_Bor vice versa. Nevertheless, the results we are going to provide do not depend on such an assumption.

I Aplayon G from q is an infinite path ρ on G with initial state q (infinite games). We assume A to choose the next state when we are in a Q_Astate and b to choose it when we are in a QB state.

I Agameis a pair (G, W), where G = (Q, Q_A, E) is a game graph and W ⊆ Q^ωis the winning condition for player B. Player Bwins the playρ = q0q₁q₂· · · if ρ ∈ W, otherwise A wins ρ.

I We are interested in winning conditions which can be expressed in afiniteway (finitely describable).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

I

I Thegame graph(arena) is a graph G = (Q, Q_A, E), with Q_A⊆ Q and E⊆ Q × Q, where ∀q ∈ Q : qE 6= ∅ (no deadlock). Let Q_B= Q\ QA. We will only consider finite game graphs.

Moreover, by construction, each edge leads from a state in QAto a state in Q_Bor vice versa. Nevertheless, the results we are going to provide do not depend on such an assumption.

I Aplayon G from q is an infinite path ρ on G with initial state q (infinite games). We assume A to choose the next state when we are in a Q_Astate and b to choose it when we are in a QBstate.

I Agameis a pair (G, W), where G = (Q, Q_A, E) is a game graph and W ⊆ Q^ωis the winning condition for player B. Player Bwins the playρ = q0q₁q₂· · · if ρ ∈ W, otherwise A wins ρ.

I We are interested in winning conditions which can be expressed in afiniteway (finitely describable).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

I

I Thegame graph(arena) is a graph G = (Q, Q_A, E), with Q_A⊆ Q and E⊆ Q × Q, where ∀q ∈ Q : qE 6= ∅ (no deadlock). Let Q_B= Q\ QA. We will only consider finite game graphs.

Moreover, by construction, each edge leads from a state in QAto a state in Q_Bor vice versa. Nevertheless, the results we are going to provide do not depend on such an assumption.

I Aplayon G from q is an infinite path ρ on G with initial state q (infinite games). We assume A to choose the next state when we are in a Q_Astate and b to choose it when we are in a QBstate.

I Agameis a pair (G, W), where G = (Q, Q_A, E) is a game graph and W⊆ Q^ω is the winning condition for player B. Player Bwins the playρ = q0q₁q₂· · · if ρ ∈ W, otherwise A wins ρ.

I We are interested in winning conditions which can be expressed in afiniteway (finitely describable).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

I

I Thegame graph(arena) is a graph G = (Q, Q_A, E), with Q_A⊆ Q and E⊆ Q × Q, where ∀q ∈ Q : qE 6= ∅ (no deadlock). Let Q_B= Q\ QA. We will only consider finite game graphs.

Moreover, by construction, each edge leads from a state in QAto a state in Q_Bor vice versa. Nevertheless, the results we are going to provide do not depend on such an assumption.

I Aplayon G from q is an infinite path ρ on G with initial state q (infinite games). We assume A to choose the next state when we are in a Q_Astate and b to choose it when we are in a QBstate.

I Agameis a pair (G, W), where G = (Q, Q_A, E) is a game graph and W⊆ Q^ω is the winning condition for player B. Player Bwins the playρ = q0q₁q₂· · · if ρ ∈ W, otherwise A wins ρ.

I We are interested in winning conditions which can be expressed in afiniteway (finitely describable).

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

M

,

M

,

I Muller games: the winning condition is a collection of sets of statesF ⊆ 2^Qsuch that B wins ρ if and only if Inf(ρ)∈ F.

I Weak Muller games: there exists a weak version of the winning condition of Muller games (Staiger-Wagner condition), according to which B wins ρ if and only if Occ(ρ)∈ F, where Occ(ρ) = {q ∈ Q : ∃i(ρ(i) = q}).

I Reachability games: given F⊆ Q in (Q, QA, E), B wins ρ if some state in ρ belongs to F.

Reachability games can be easily expressed in terms of Staiger-Wagner condition:F = {R ⊆ Q : R ∩ F 6= ∅}.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

M

,

M

,

I Muller games: the winning condition is a collection of sets of statesF ⊆ 2^Qsuch that B wins ρ if and only if Inf(ρ)∈ F.

I Weak Muller games: there exists a weak version of the winning condition of Muller games (Staiger-Wagner condition), according to which B wins ρ if and only if Occ(ρ)∈ F, where Occ(ρ) = {q ∈ Q : ∃i(ρ(i) = q}).

I Reachability games: given F⊆ Q in (Q, QA, E), B wins ρ if some state in ρ belongs to F.

Reachability games can be easily expressed in terms of Staiger-Wagner condition:F = {R ⊆ Q : R ∩ F 6= ∅}.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

M

,

M

,

I Muller games: the winning condition is a collection of sets of statesF ⊆ 2^Qsuch that B wins ρ if and only if Inf(ρ)∈ F.

I Weak Muller games: there exists a weak version of the winning condition of Muller games (Staiger-Wagner condition), according to which B wins ρ if and only if Occ(ρ)∈ F, where Occ(ρ) = {q ∈ Q : ∃i(ρ(i) = q}).

I Reachability games: given F⊆ Q in (Q, QA, E), B wins ρ if some state in ρ belongs to F.

Reachability games can be easily expressed in terms of Staiger-Wagner condition:F = {R ⊆ Q : R ∩ F 6= ∅}.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

M

,

M

,

I Muller games: the winning condition is a collection of sets of statesF ⊆ 2^Qsuch that B wins ρ if and only if Inf(ρ)∈ F.

I Weak Muller games: there exists a weak version of the winning condition of Muller games (Staiger-Wagner condition), according to which B wins ρ if and only if Occ(ρ)∈ F, where Occ(ρ) = {q ∈ Q : ∃i(ρ(i) = q}).

I Reachability games: given F⊆ Q in (Q, QA, E), B wins ρ if some state in ρ belongs to F.

Reachability games can be easily expressed in terms of Staiger-Wagner condition:F = {R ⊆ Q : R ∩ F 6= ∅}.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

S

,

,

,

I Astrategyfor a player is a mapping f : Q⁺→ Q such that, given the history of the game up a certain state (under his/her control), specifies his/her behavior at the next step.

I A strategy f for player B from q is awinning strategyif each play from q, played according to f , is won by player B.

I W_B:={q ∈ Q | B wins starting from q} is said thewinning region of B (the same for A). Obviously, WA∩ WB =∅.

I If W_A∪ WB= Q, we say that the game isdetermined.

THE SYNTHESIS PROBLEM INFINITE GAMES ANDB ¨UCHI-LANDWEBER THEOREM

S

,

,

,

I Astrategyfor a player is a mapping f : Q⁺→ Q such that, given the history of the game up a certain state (under his/her control), specifies his/her behavior at the next step.

I A strategy f for player B from q is awinning strategyif each play from q, played according to f , is won by player B.

I W_B:={q ∈ Q | B wins starting from q} is said thewinning region of B (the same for A). Obviously, WA∩ WB =∅.

I If W_A∪ WB= Q, we say that the game isdetermined.