The monadic theory of two successors Gabriele Puppis

The monadic theory of two successors

Gabriele Puppis

LaBRI / CNRS

Decidability of S2S (Rabin’69)

One can decide if a sentence of MSO[EMSO[EMSO[E₁₁₁, E, E, E₂₂₂]]] holds over the binary tree.

Same approach as with (N, +1): transform formulas to automata q₀

q₁ q₂

... ... ... ...

... ... ... ... ... ... ... ...

Decidability of S2S (Rabin’69)

One can decide if a sentence of MSO[EMSO[EMSO[E₁₁₁, E, E, E₂₂₂]]] holds over the binary tree.

Same approach as with (N, +1): transform formulas to automata

0 00

1 1

1 000

0

00 111 111 111

0 0

0 000 111 000 000 000 000 111 q₀

q₁ q₂

... ... ... ...

... ... ... ... ... ... ... ...

Decidability of S2S (Rabin’69)

One can decide if a sentence of MSO[EMSO[EMSO[E₁₁₁, E, E, E₂₂₂]]] holds over the binary tree.

Same approach as with (N, +1): transform formulas to automata

0 00

1 1

1 000

0

00 111 111 111

0 0

0 000 111 000 000 000 000 111 q₀

q₁ q₂

... ... ... ...

... ... ... ... ... ... ... ...

Decidability of S2S (Rabin’69)

One can decide if a sentence of MSO[EMSO[EMSO[E₁₁₁, E, E, E₂₂₂]]] holds over the binary tree.

Same approach as with (N, +1): transform formulas to automata

0 00

1 1

1 000

0

00 111 111 111

0 0

0 000 111 000 000 000 000 111 q₀

q₁ q₂

... ... ... ...

... ... ... ... ... ... ... ...

Decidability of S2S (Rabin’69)

One can decide if a sentence of MSO[EMSO[EMSO[E₁₁₁, E, E, E₂₂₂]]] holds over the binary tree.

Same approach as with (N, +1): transform formulas to automata

0 00

1 1

1 000

0

00 111 111 111

0 0

0 000 111 000 000 000 000 111 q₀

q₁ q₂

... ... ... ...

... ... ... ... ... ... ... ...

Decidability of S2S (Rabin’69)

One can decide if a sentence of MSO[EMSO[EMSO[E₁₁₁, E, E, E₂₂₂]]] holds over the binary tree.

Same approach as with (N, +1): transform formulas to automata

0 00

1 1

1 000

0

00 111 111 111

0 0

0 000 111 000 000 000 000 111 q₀

q₁ q₂

... ... ... ...

... ... ... ... ... ... ... ...

Definition

A tree automaton is a tuple A = (Q, Σ, ∆, I , Ω), where Q is a finite set of control states

Σ is a finite alphabet for transition labels

∆ ⊆ Q × Σ × QQQ²²² is a finite set of transition rules I ⊆ Q is a set of initial states

Ω ⊆ Q^ω defines the acceptance condition by specifying the allowed sequences of states along all pathsall pathsall paths in the tree (more details in the next slide...)

E.g. in a B¨uchi tree automaton one has

Ω = { ρ ∈ Q^ω ∣ inf(ρ) ∩ F ≠ ∅ }

Need ofnon-determinismandstronger acceptance conditions

∃X . X is a path ∧ ∃∃X . X is a path ∧ ∃∃X . X is a path ∧ ∃^∞∞∞y ∈ X . a(y )y ∈ X . a(y )y ∈ X . a(y )

complement? yep!

a a a a

a

⋮

a a

a a a

a a a a

⋮

Need ofnon-determinismandstronger acceptance conditions

∃X . X is a path ∧ ∃∃X . X is a path ∧ ∃∃X . X is a path ∧ ∃^∞∞∞y ∈ X . a(y )y ∈ X . a(y )y ∈ X . a(y ) complement?

yep!

a a a a

a

⋮

a a

a a a

a a a a

⋮

Need ofnon-determinismandstronger acceptance conditions

∃X . X is a path ∧ ∃∃X . X is a path ∧ ∃∃X . X is a path ∧ ∃^∞∞∞y ∈ X . a(y )y ∈ X . a(y )y ∈ X . a(y )

complement? yep!

a a a a

a

⋮

a a

a a a

a a a a

⋮

Need ofnon-determinismandstronger acceptance conditions

∃X . X is a path ∧ ∃∃X . X is a path ∧ ∃∃X . X is a path ∧ ∃^∞∞∞y ∈ X . a(y )y ∈ X . a(y )y ∈ X . a(y )

complement? yep!

a a a a

a

⋮

a a

a a a

a a a a

⋮ B¨uchi condition:

non final

states final

states

Parity condition:

odd even odd even

Decidability of S2S (Rabin’69)

One can decide if a sentence of MSO[EMSO[EMSO[E111, E, E, E222]]] holds over the binary tree.

By induction on all subformulas ϕ(X₁, ..., X_m), construct tree automata Aϕsuch that

L (Aϕ) = {t ∈ Σ^{1,2}m ^⋆ ∣t ⊧ ϕ}

L (A^ϕ) = {t ∈ Σ^{1,2}

⋆

m ∣t ⊧ ϕ}

L (Aϕ) = {t ∈ Σ^{1,2}m ^⋆ ∣ t ⊧ ϕ}

logical disjunction ∨∨∨ ↦ union existential quantification ∃∃∃ ↦ projection

logical negation ¬¬¬ ↦ complementation

Complementation via parity games: Automaton vs Pathfinder

q0↦q1, q2

left

Complementation via parity games: Automaton vs Pathfinder

q0↦q1, q2

left

Complementation via parity games: Automaton vs Pathfinder

q0↦q1, q2

q1↦q3, q4

left

Complementation via parity games: Automaton vs Pathfinder

q0↦q1, q2

q1↦q3, q4

left

right

Complementation via parity games: Automaton vs Pathfinder

q0↦q1, q2

q1↦q3, q4

q4↦...

...

left

right

...

Positional determinacy of parity games

Either Automaton wins with a positional strategy, or Pathfinder does.

When a tree is rejected, Pathfinder’s winning strategy can be converted to a strategy for Automaton over a game with new transition rules

t /∈L (A) t /∈L (A) t /∈L (A)

iff Pathfinder has a winning positional strategy σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2} (or, equally, σ ∶ {1, 2}σ ∶ {1, 2}σ ∶ {1, 2}^⋆⋆⋆→ {1, 2}→ {1, 2}→ {1, 2}^∆∆∆)

iff

iff t ∈t ∈t ∈L (AL (AL (A^CCC)))

Positional determinacy of parity games

Either Automaton wins with a positional strategy, or Pathfinder does.

When a tree is rejected, Pathfinder’s winning strategy can be converted to a strategy for Automaton over a game with new transition rules

t /∈L (A) t /∈L (A) t /∈L (A)

iff Pathfinder has a winning positional strategy σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2} (or, equally, σ ∶ {1, 2}σ ∶ {1, 2}σ ∶ {1, 2}^⋆⋆⋆→ {1, 2}→ {1, 2}→ {1, 2}^∆∆∆)

iff

iff t ∈t ∈t ∈L (AL (AL (A^CCC)))

Positional determinacy of parity games

Either Automaton wins with a positional strategy, or Pathfinder does.

When a tree is rejected, Pathfinder’s winning strategy can be converted to a strategy for Automaton over a game with new transition rules

t /∈L (A) t /∈L (A) t /∈L (A)

iff Pathfinder has a winning positional strategy σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2} (or, equally, σ ∶ {1, 2}σ ∶ {1, 2}σ ∶ {1, 2}^⋆⋆⋆→ {1, 2}→ {1, 2}→ {1, 2}^∆∆∆) iff

iff t ∈t ∈t ∈L (AL (AL (A^CCC)))

∃t ⊗ σ ∶ {1, 2}^⋆→Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆ expansion of t such that

∀infinite path π ∈ {1, 2}^ω

∀seq. of transitions τ ∈ ∆^ω

if π is consistent with (t ⊗ σ)∣π and τ , then τ violates parity condition of A

Positional determinacy of parity games

Either Automaton wins with a positional strategy, or Pathfinder does.

When a tree is rejected, Pathfinder’s winning strategy can be converted to a strategy for Automaton over a game with new transition rules

t /∈L (A) t /∈L (A) t /∈L (A)

iff Pathfinder has a winning positional strategy σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2} (or, equally, σ ∶ {1, 2}σ ∶ {1, 2}σ ∶ {1, 2}^⋆⋆⋆→ {1, 2}→ {1, 2}→ {1, 2}^∆∆∆) iff

iff t ∈t ∈t ∈L (AL (AL (A^CCC)))

∃t ⊗ σ ∶ {1, 2}^⋆→Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆ expansion of t such that

∀infinite path π ∈ {1, 2}^ω

∀seq. of transitions τ ∈ ∆^ω

if π is consistent with (t ⊗ σ)∣π and τ , then τ violates parity condition of A

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

Positional determinacy of parity games

Either Automaton wins with a positional strategy, or Pathfinder does.

When a tree is rejected, Pathfinder’s winning strategy can be converted to a strategy for Automaton over a game with new transition rules

t /∈L (A) t /∈L (A) t /∈L (A)

iff Pathfinder has a winning positional strategy σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2} (or, equally, σ ∶ {1, 2}σ ∶ {1, 2}σ ∶ {1, 2}^⋆⋆⋆→ {1, 2}→ {1, 2}→ {1, 2}^∆∆∆) iff

iff t ∈t ∈t ∈L (AL (AL (A^CCC)))

∃t ⊗ σ ∶ {1, 2}^⋆→Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆ expansion of t such that

∀infinite path π ∈ {1, 2}^ω

∀seq. of transitions τ ∈ ∆^ω

if π is consistent with (t ⊗ σ)∣π and τ , then τ violates parity condition of A

deterministic deterministic deterministic parity word parity word parity word automaton over automaton over automaton over {1, 2}×Σ×{1, 2}^∆ {1, 2}×Σ×{1, 2}^∆ {1, 2}×Σ×{1, 2}^∆ regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

Positional determinacy of parity games

Either Automaton wins with a positional strategy, or Pathfinder does.

When a tree is rejected, Pathfinder’s winning strategy can be converted to a strategy for Automaton over a game with new transition rules

t /∈L (A) t /∈L (A) t /∈L (A)

iff Pathfinder has a winning positional strategy σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2} (or, equally, σ ∶ {1, 2}σ ∶ {1, 2}σ ∶ {1, 2}^⋆⋆⋆→ {1, 2}→ {1, 2}→ {1, 2}^∆∆∆) iff

iff t ∈t ∈t ∈L (AL (AL (A^CCC)))

∃t ⊗ σ ∶ {1, 2}^⋆→Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆ expansion of t such that

∀infinite path π ∈ {1, 2}^ω

∀seq. of transitions τ ∈ ∆^ω

if π is consistent with (t ⊗ σ)∣π and τ , then τ violates parity condition of A

parity parity parity treetree tree automaton automaton automaton over over over Σ×{1, 2}^∆ Σ×{1, 2}^∆ Σ×{1, 2}^∆

deterministic deterministic deterministic parity word parity word parity word automaton over automaton over automaton over {1, 2}×Σ×{1, 2}^∆ {1, 2}×Σ×{1, 2}^∆ {1, 2}×Σ×{1, 2}^∆ regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

Positional determinacy of parity games

Either Automaton wins with a positional strategy, or Pathfinder does.

When a tree is rejected, Pathfinder’s winning strategy can be converted to a strategy for Automaton over a game with new transition rules

t /∈L (A) t /∈L (A) t /∈L (A)

iff Pathfinder has a winning positional strategy σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2}

σ ∶ {1, 2}^⋆×∆ → {1, 2} (or, equally, σ ∶ {1, 2}σ ∶ {1, 2}σ ∶ {1, 2}^⋆⋆⋆→ {1, 2}→ {1, 2}→ {1, 2}^∆∆∆) iff

iff t ∈t ∈t ∈L (AL (AL (A^CCC)))

∃t ⊗ σ ∶ {1, 2}^⋆→Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆

∃t ⊗ σ ∶ {1, 2}^⋆ →Σ × {1, 2}^∆ expansion of t such that

∀infinite path π ∈ {1, 2}^ω

∀seq. of transitions τ ∈ ∆^ω

if π is consistent with (t ⊗ σ)∣π and τ , then τ violates parity condition of A

parity parity parity treetree tree automaton automaton automaton over over over Σ×{1, 2}^∆ Σ×{1, 2}^∆ Σ×{1, 2}^∆

deterministic deterministic deterministic parity word parity word parity word automaton over automaton over automaton over {1, 2}×Σ×{1, 2}^∆ {1, 2}×Σ×{1, 2}^∆ {1, 2}×Σ×{1, 2}^∆ regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

regular ω-language over {1, 2}×Σ×{1, 2}^∆×∆

Application example 1 (interpretation of the ternary tree) Consider the binary tree t₂

Inside t₂one can logically define the ternary tree t₃

1 select a subset of the vertices that will form the nodes of t₃ ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆

ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆ ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆

2 define the three successor relations of t3 by the formulas ϕ1(x , y ) = (x , y ) ∈ E1

ϕ₁(x , y ) = (x , y ) ∈ E₁

ϕ1(x , y ) = (x , y ) ∈ E1 ϕϕϕ_2/32/32/3(x , y ) = (x , y ) ∈ (E(x , y ) = (x , y ) ∈ (E(x , y ) = (x , y ) ∈ (E₂22○○○EEE_1/21/21/2))) Decidability of S3S

One can decide MSO[EMSO[EMSO[E111, E, E, E222, E, E, E333]]] over the ternary tree.

Application example 1 (interpretation of the ternary tree) Consider the binary tree t₂

Inside t₂one can logically define the ternary tree t₃

1 select a subset of the vertices that will form the nodes of t₃ ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆

ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆ ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆

2 define the three successor relations of t3 by the formulas ϕ1(x , y ) = (x , y ) ∈ E1

ϕ₁(x , y ) = (x , y ) ∈ E₁

ϕ1(x , y ) = (x , y ) ∈ E1 ϕϕϕ_2/32/32/3(x , y ) = (x , y ) ∈ (E(x , y ) = (x , y ) ∈ (E(x , y ) = (x , y ) ∈ (E₂22○○○EEE_1/21/21/2))) Decidability of S3S

One can decide MSO[EMSO[EMSO[E111, E, E, E222, E, E, E333]]] over the ternary tree.

Application example 1 (interpretation of the ternary tree) Consider the binary tree t₂

Inside t₂one can logically define the ternary tree t₃

1 select a subset of the vertices that will form the nodes of t₃ ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆

ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆ ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆

2 define the three successor relations of t3by the formulas ϕ1(x , y ) = (x , y ) ∈ E1

ϕ1(x , y ) = (x , y ) ∈ E1

ϕ1(x , y ) = (x , y ) ∈ E1 ϕϕϕ_2/32/32/3(x , y ) = (x , y ) ∈ (E(x , y ) = (x , y ) ∈ (E(x , y ) = (x , y ) ∈ (E222○○○EEE_1/21/21/2)))

Decidability of S3S

One can decide MSO[EMSO[EMSO[E111, E, E, E222, E, E, E333]]] over the ternary tree.

Application example 1 (interpretation of the ternary tree) Consider the binary tree t₂

Inside t₂one can logically define the ternary tree t₃

1 select a subset of the vertices that will form the nodes of t₃ ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆

ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆ ϕ_dom(x ) = (root, x ) ∈ (E₁ ∪ E₂○E₁ ∪ E₂○E₂)^⋆

2 define the three successor relations of t3by the formulas ϕ1(x , y ) = (x , y ) ∈ E1

ϕ1(x , y ) = (x , y ) ∈ E1

ϕ1(x , y ) = (x , y ) ∈ E1 ϕϕϕ_2/32/32/3(x , y ) = (x , y ) ∈ (E(x , y ) = (x , y ) ∈ (E(x , y ) = (x , y ) ∈ (E222○○○EEE_1/21/21/2))) Decidability of S3S

One can decide MSO[EMSO[EMSO[E111, E, E, E222, E, E, E333]]] over the ternary tree.

Application example 2 (interpretation of the rationals) Consider again the binary tree t₂

Inside t₂one can logically define the the rationals QQQ

the dense order on Q can be seen as the infix order of t2

ϕ_≤(x , y ) ϕ_≤(x , y )

ϕ_≤(x , y ) = ∃z .∃z .∃z . ((z , x ) ∈ E((z , x ) ∈ E((z , x ) ∈ E₁₁1○ (E○ (E○ (E1₁₁∪∪∪EEE₂2₂)))^⋆⋆⋆ ∨∨∨ z = x )z = x )z = x )

∧∧

∧ ((z , y ) ∈ E((z , y ) ∈ E((z , y ) ∈ E₂₂₂○ (E○ (E○ (E₁₁₁∪∪∪EEE₂₂₂)))^⋆⋆⋆ ∨∨∨ z = y )z = y )z = y )

Monadic theories of linear orders (Shelah ’75) One can decide MSO[≤]MSO[≤]MSO[≤] over QQQ and

over the class of all countable linear orders. One cannot decide MSO[≤]MSO[≤]MSO[≤] over RRR.

Application example 2 (interpretation of the rationals) Consider again the binary tree t₂

Inside t₂one can logically define the the rationals QQQ

the dense order on Q can be seen as the infix order of t2

ϕ_≤(x , y ) ϕ_≤(x , y )

ϕ_≤(x , y ) = ∃z .∃z .∃z . ((z , x ) ∈ E((z , x ) ∈ E((z , x ) ∈ E₁₁1○ (E○ (E○ (E1₁₁∪∪∪EEE₂2₂)))^⋆⋆⋆ ∨∨∨ z = x )z = x )z = x )

∧∧

∧ ((z , y ) ∈ E((z , y ) ∈ E((z , y ) ∈ E₂₂₂○ (E○ (E○ (E₁₁₁∪∪∪EEE₂₂₂)))^⋆⋆⋆ ∨∨∨ z = y )z = y )z = y ) Monadic theories of linear orders (Shelah ’75)

One can decide MSO[≤]MSO[≤]MSO[≤] over QQQ and

over the class of all countable linear orders.

One cannot decide MSO[≤]MSO[≤]MSO[≤] over RRR.

Application example 3 (interpretation of a pushdown system)

B

Bα

Bβ

Bα

Bαβ

Bβα

Bββ . . .

. . .

. . .

. . . ε

ε

ε

ε

ε

ε

ε A

Aα

Aβ

Aα

Aαβ

Aβα

Aββ . . .

. . .

. . .

. . . popα

popβ

pop α pop β

pop α pop β pushα

pushβ

push α push β

push α push β

Any property of the above system expressed by an MSO formula

ψ = ... ∀X∀X∀X ... ( yyy ÐÐÐ^{push βpush βpush β}ÐÐÐÐÐÐÐÐÐ→→→zzz ) ... ( y ↓y ↓y ↓ε_εεzzz ) ... ( zzz ←ÐÐÐ←ÐÐÐ←ÐÐÐ^{pop βpop βpop β} yyy ) ...

can be translated into an equi-satisfiable formula over the binary tree ψ = ... ∀Xˆ ∀X∀X₁₁₁, X, X, X₂₂₂ ... ( (y(y(y₁₁₁, z, z, z₁₁₁) ∈) ∈) ∈EEE₂₂₂)... ( yyy₁₁₁===zzz₂₂₂)... ( (y(y(y₂₂₂, z, z, z₂₂₂) ∈) ∈) ∈EEE₂₂₂)...

Next