First-order theories Gabriele Puppis

First-order theories

Gabriele Puppis

LaBRI / CNRS

Definition

Fix a class C of structures (e.g. graphs) and a logic L (e.g. FO).

The LLL-theory of CCC is the set of all formulas in L that can be satisfied by some structure inC .

The theory is decidable if there is an algorithm that receives formulas as input and tells whether they are in the theory or not.

Examples

first-order theory of the class of all graphs monadic theory of the class of all linear orders monadic theory of N

monadic theory of the grid

Definition

Fix a class C of structures (e.g. graphs) and a logic L (e.g. FO).

The LLL-theory of CCC is the set of all formulas in L that can be satisfied by some structure inC .

The theory is decidable if there is an algorithm that receives formulas as input and tells whether they are in the theory or not.

Examples

first-order theory of the class of all graphs monadic theory of the class of all linear orders monadic theory of N

monadic theory of the grid

Undecidability of first-order theory

One cannot decide whether a given formula of FO[Σ, E1, E₂]

FO[Σ, E1, E2]

FO[Σ, E1, E₂] is satisfied over some labelled gridlabelled gridlabelled grid.

(and equally for MSO[EMSO[EMSO[E1₁₁, E, E, E₂₂2]]]over the grid N × NN × NN × N)

Given a Turing machine M, construct ψψψ_MM_M defining its halting runs:

1 encode initial configuration by top row

2 encode next configurations by next rows

3 find a row with halting configuration

MSO can even guess the labelling!

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

⋮ ⋮ ⋮ ⋮

⋯

⋯

⋯

⋯ q_halt ⋱

qqhalt_halt

Undecidability of first-order theory

One cannot decide whether a given formula of FO[Σ, E1, E₂]

FO[Σ, E1, E2]

FO[Σ, E1, E₂] is satisfied over some labelled gridlabelled gridlabelled grid.

(and equally for MSO[EMSO[EMSO[E1₁₁, E, E, E₂₂2]]]over the grid N × NN × NN × N)

Given a Turing machine M, construct ψψψ_MM_M defining its halting runs:

1 encode initial configuration by top row

2 encode next configurations by next rows

3 find a row with halting configuration

MSO can even guess the labelling!

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

⋮ ⋮ ⋮ ⋮

⋯

⋯

⋯

⋯ q_halt ⋱

qqhalt_halt

Undecidability of first-order theory

One cannot decide whether a given formula of FO[Σ, E1, E₂]

FO[Σ, E1, E2]

FO[Σ, E1, E₂] is satisfied over some labelled gridlabelled gridlabelled grid.

(and equally for MSO[EMSO[EMSO[E1₁₁, E, E, E₂₂2]]]over the grid N × NN × NN × N)

Given a Turing machine M, construct ψψψ_MM_M defining its halting runs:

1 encode initial configuration by top row

2 encode next configurations by next rows

3 find a row with halting configuration

MSO can even guess the labelling!

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

⋮ ⋮ ⋮ ⋮

⋯

⋯

⋯

⋯

⋱ q0

q0

q0 ⊔⊔⊔ ⊔⊔⊔ ⊔⊔⊔

q_halt qqhalt_halt

Undecidability of first-order theory

One cannot decide whether a given formula of FO[Σ, E1, E₂]

FO[Σ, E1, E2]

FO[Σ, E1, E₂] is satisfied over some labelled gridlabelled gridlabelled grid.

(and equally for MSO[EMSO[EMSO[E1₁₁, E, E, E₂₂2]]]over the grid N × NN × NN × N)

Given a Turing machine M, construct ψψψ_MM_M defining its halting runs:

1 encode initial configuration by top row

2 encode next configurations by next rows

3 find a row with halting configuration

MSO can even guess the labelling!

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

⋮ ⋮ ⋮ ⋮

⋯

⋯

⋯

⋯

⋱ q0

q0

q0 ⊔⊔⊔ ⊔⊔⊔ ⊔⊔⊔ aaa qqq₁₁₁ ⊔⊔⊔ ⊔⊔⊔ aaa bbb qqq₂2₂ ⊔⊔⊔ aaa qqq3₃3 bbb ⊔⊔⊔

q_halt qqhalt_halt

Undecidability of first-order theory

One cannot decide whether a given formula of FO[Σ, E1, E₂]

FO[Σ, E1, E2]

FO[Σ, E1, E₂] is satisfied over some labelled gridlabelled gridlabelled grid.

(and equally for MSO[EMSO[EMSO[E1₁₁, E, E, E₂₂2]]]over the grid N × NN × NN × N)

Given a Turing machine M, construct ψψψ_MM_M defining its halting runs:

1 encode initial configuration by top row

2 encode next configurations by next rows

3 find a row with halting configuration

MSO can even guess the labelling!

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

⋮ ⋮ ⋮ ⋮

⋯

⋯

⋯

⋯

⋱ q0

q0

q0 ⊔⊔⊔ ⊔⊔⊔ ⊔⊔⊔ aaa qqq₁₁₁ ⊔⊔⊔ ⊔⊔⊔ aaa bbb qqq₂2₂ ⊔⊔⊔ aaa qqq3₃3 bbb ⊔⊔⊔

q_halt qqhalt_halt

Undecidability of first-order theory

One cannot decide whether a given formula of FO[Σ, E1, E₂]

FO[Σ, E1, E2]

FO[Σ, E1, E₂] is satisfied over some labelled gridlabelled gridlabelled grid.

(and equally for MSO[EMSO[EMSO[E1₁₁, E, E, E₂₂2]]]over the grid N × NN × NN × N)

Given a Turing machine M, construct ψψψ_MM_M defining its halting runs:

1 encode initial configuration by top row

2 encode next configurations by next rows

3 find a row with halting configuration

MSO can even guess the labelling!

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

⋮ ⋮ ⋮ ⋮

⋯

⋯

⋯

⋯

⋱ q0

q0

q0 ⊔⊔⊔ ⊔⊔⊔ ⊔⊔⊔ aaa qqq₁₁₁ ⊔⊔⊔ ⊔⊔⊔ aaa bbb qqq₂2₂ ⊔⊔⊔ aaa qqq3₃3 bbb ⊔⊔⊔

q_halt qqhalt_halt

Undecidability of first-order theory

One cannot decide whether a given formula of FO[Σ, E1, E₂]

FO[Σ, E1, E2]

FO[Σ, E1, E₂] is satisfied over some labelled gridlabelled gridlabelled grid.

(and equally for MSO[EMSO[EMSO[E1₁₁, E, E, E₂₂2]]]over the grid N × NN × NN × N)

Given a Turing machine M, construct ψψψ_MM_M defining its halting runs:

1 encode initial configuration by top row

2 encode next configurations by next rows

3 find a row with halting configuration

MSO can even guess the labelling!

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

●

⋮ ⋮ ⋮ ⋮

⋯

⋯

⋯

⋯

⋱ q0

q0

q0 ⊔⊔⊔ ⊔⊔⊔ ⊔⊔⊔ aaa qqq₁₁₁ ⊔⊔⊔ ⊔⊔⊔ aaa bbb qqq₂2₂ ⊔⊔⊔ aaa qqq3₃3 bbb ⊔⊔⊔

q_halt qqhalt_halt

Consequences (Church ’36, Turing ’37, Trakhtenbrot ’50, ...) The FO theory of the class of all finite structures is undecidable (provided that signature contains a binary predicate besides =).

The MSO theory of any class of graphs with unbounded grids as minors

unbounded grids as minorsunbounded grids as minors is undecidable. The MSO theory of (N, +)((N, +)N, +) is undecidable.

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

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

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

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

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

n

4n+20

Consequences (Church ’36, Turing ’37, Trakhtenbrot ’50, ...) The FO theory of the class of all finite structures is undecidable (provided that signature contains a binary predicate besides =).

The MSO theory of any class of graphs with unbounded grids as minors

unbounded grids as minorsunbounded grids as minors is undecidable.

The MSO theory of (N, +)((N, +)N, +) is undecidable.

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

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

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

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

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

n

4n+20

Consequences (Church ’36, Turing ’37, Trakhtenbrot ’50, ...) The FO theory of the class of all finite structures is undecidable (provided that signature contains a binary predicate besides =).

The MSO theory of any class of graphs with unbounded grids as minors

unbounded grids as minorsunbounded grids as minors is undecidable.

The MSO theory of (N, +)((N, +)N, +) is undecidable.

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

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

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

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

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

⋮

n n+1 n+2 n+3 n+4

2n 2n+2 2n+4 2n+6 2n+8

3n 3n+3 3n+6 3n+9 3n+12

4n 4n+4 4n+8 4n+16 4n+20

Definition

Presburger arithmetic is the first-order theory of (N, +)((N, +)N, +)

Examples of Presburger formulas

ψ0 = ∃x . ∀y . (x + y = y ) ϕ_≤(x , y ) = ∃z . (y = x + z ) ϕ_2×(x , y ) = (x + x = y )

ψω = ∀x . ∃y . (x ≤ y ∧ ¬x = y )

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

Originally proved by quantifier elimination. Here we use automata!

1 Encode numbers x ∈ N by reverse binary expansions [x] ∈ B[[x ] ∈ Bx ] ∈ B^⋆⋆⋆ e.g. [4] = 001, [0] = ε, . . .

2 Encode sum relation + ⊆ N × N × N by language LLL+₊₊⊆ (⊆ (⊆ (B × B × B)B × B × B)B × B × B)^⋆⋆⋆ e.g. [ + (3,1,4)] = [3] ⊗ [1] ⊗ [4] = (

1 1 0) (

1 0 0) (

0 0 1)

A₊∶

p q

(

0 0 0), (¹0

1), (⁰1

1) (

1 0 0), (⁰¹

0), (¹¹

1) (

1 1 0) (

0 0 1)

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

Originally proved by quantifier elimination. Here we use automata!

1 Encode numbers x ∈ N by reverse binary expansions [x] ∈ B[[x ] ∈ Bx ] ∈ B^⋆⋆⋆ e.g. [4] = 001, [0] = ε, . . .

2 Encode sum relation + ⊆ N × N × N by language LLL+₊₊⊆ (⊆ (⊆ (B × B × B)B × B × B)B × B × B)^⋆⋆⋆ e.g. [ + (3,1,4)] = [3] ⊗ [1] ⊗ [4] = (

1 1 0) (

1 0 0) (

0 0 1)

A₊∶

p q

(

0 0 0), (¹0

1), (⁰1

1) (

1 0 0), (⁰¹

0), (¹¹

1) (

1 1 0) (

0 0 1)

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

Originally proved by quantifier elimination. Here we use automata!

1 Encode numbers x ∈ N by reverse binary expansions [x] ∈ B[[x ] ∈ Bx ] ∈ B^⋆⋆⋆ e.g. [4] = 001, [0] = ε, . . .

2 Encode sum relation + ⊆ N × N × N by language LLL+₊₊⊆ (⊆ (⊆ (B × B × B)B × B × B)B × B × B)^⋆⋆⋆ e.g. [ + (3,1,4)] = [3] ⊗ [1] ⊗ [4] = (

1 1 0) (

1 0 0) (

0 0 1)

A₊∶

p q

(

0 0 0), (¹0

1), (⁰1

1) (

1 0 0), (⁰¹

0), (¹¹

1) (

1 1 0) (

0 0 1)

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

Originally proved by quantifier elimination. Here we use automata!

1 Encode numbers x ∈ N by reverse binary expansions [x] ∈ B[[x ] ∈ Bx ] ∈ B^⋆⋆⋆ e.g. [4] = 001, [0] = ε, . . .

2 Encode sum relation + ⊆ N × N × N by language LLL+₊₊⊆ (⊆ (⊆ (B × B × B)B × B × B)B × B × B)^⋆⋆⋆ e.g. [ + (3,1,4)] = [3] ⊗ [1] ⊗ [4] = (

1 1 0) (

1 0 0) (

0 0 1)

A₊∶

p q

(

0 0 0), (¹0

1), (⁰1

1) (

1 0 0), (⁰¹

0), (¹¹

1) (

1 1 0) (

0 0 1)

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

We inductively translate every Presburger formula ϕ(x1, ..., xm) into a finite automaton A_ϕ over Σm =B^m such that

L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } L (Aϕ) = { [x₁] ⊗ ⋅ ⋅ ⋅ ⊗ [x_m] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., x_m) } L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } so as to reduce satisfiability of ϕ to emptiness of L(Aϕ).

For atomic formulas x = y and +(x , y , z ), use automata A₌and A₊ For disjunction ϕ1(¯x ) ∨ ϕ2(¯x ), compute union of Aϕ₁ and Aϕ₂

For negation ¬ϕ(¯x ), compute the complement of Aϕ

For existential quantification ∃y . ϕ(¯x , y ), project Aϕ from Σm+1 to Σm

(×¹¹¹000⁾ (¹¹¹

1 1

×1)

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

We inductively translate every Presburger formula ϕ(x1, ..., xm) into a finite automaton A_ϕ over Σm =B^m such that

L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } L (Aϕ) = { [x₁] ⊗ ⋅ ⋅ ⋅ ⊗ [x_m] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., x_m) } L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } so as to reduce satisfiability of ϕ to emptiness of L(Aϕ).

For atomic formulas x = y and +(x , y , z ), use automata A=and A+

For disjunction ϕ1(¯x ) ∨ ϕ2(¯x ), compute union of Aϕ₁ and Aϕ₂

For negation ¬ϕ(¯x ), compute the complement of Aϕ

For existential quantification ∃y . ϕ(¯x , y ), project Aϕ from Σm+1 to Σm

(×¹¹¹000⁾ (¹¹¹

1 1

×1)

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

We inductively translate every Presburger formula ϕ(x1, ..., xm) into a finite automaton A_ϕ over Σm =B^m such that

L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } L (Aϕ) = { [x₁] ⊗ ⋅ ⋅ ⋅ ⊗ [x_m] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., x_m) } L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } so as to reduce satisfiability of ϕ to emptiness of L(Aϕ).

For atomic formulas x = y and +(x , y , z ), use automata A=and A+

For disjunction ϕ1(¯x ) ∨ ϕ2(¯x ), compute union of Aϕ₁ and Aϕ₂

For negation ¬ϕ(¯x ), compute the complement of Aϕ

For existential quantification ∃y . ϕ(¯x , y ), project Aϕ from Σm+1 to Σm

(×¹¹¹000⁾ (¹¹¹

1 1

×1)

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

We inductively translate every Presburger formula ϕ(x1, ..., xm) into a finite automaton A_ϕ over Σm =B^m such that

L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } L (Aϕ) = { [x₁] ⊗ ⋅ ⋅ ⋅ ⊗ [x_m] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., x_m) } L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } so as to reduce satisfiability of ϕ to emptiness of L(Aϕ).

For atomic formulas x = y and +(x , y , z ), use automata A=and A+

For disjunction ϕ1(¯x ) ∨ ϕ2(¯x ), compute union of Aϕ₁ and Aϕ₂

For negation ¬ϕ(¯x ), compute the complement of Aϕ

For existential quantification ∃y . ϕ(¯x , y ), project Aϕ from Σm+1 to Σm

(×¹¹¹000⁾ (¹¹¹

1 1

×1)

Decidability of Presburger arithmetic (Presburger ’29) One can decide if a Presburger sentence ψ holds over (N, +).

We inductively translate every Presburger formula ϕ(x1, ..., xm) into a finite automaton A_ϕ over Σm =B^m such that

L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } L (Aϕ) = { [x₁] ⊗ ⋅ ⋅ ⋅ ⊗ [x_m] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., x_m) } L (Aϕ) = { [x1] ⊗ ⋅ ⋅ ⋅ ⊗ [xm] ∈Σ^⋆_m ∣ (N, +) ⊧ ϕ(x¹, ..., xm) } so as to reduce satisfiability of ϕ to emptiness of L(Aϕ).

For atomic formulas x = y and +(x , y , z ), use automata A=and A+

For disjunction ϕ1(¯x ) ∨ ϕ2(¯x ), compute union of Aϕ₁ and Aϕ₂

For negation ¬ϕ(¯x ), compute the complement of Aϕ

For existential quantification ∃y . ϕ(¯x , y ), project Aϕ from Σm+1 to Σm

(×¹¹¹000⁾ (¹¹¹

1 1

×1)

Example of translation

Consider the (unsatisfiable) formula

ψ = ∃x .¬∃y . (y =x +1) ψ = ∃x . ¬∃y . (y =x+1) ψ = ∃x .¬∃y . (y =x+1)

1 Start from automaton A_{yyy=x+1=x+1=x+1}

2 Project away the encoding of yyy, thus capturing∃y .∃y .∃y .(y(y(y ===xxx+++1)1)1)

3 Complement the det. automaton, thus capturing ¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

4 Project away the encoding of xxx, thus getting ∃x .∃x .∃x .¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

p q

(¹¹¹

0 00)

(⁰⁰⁰

111)

(⁰⁰⁰₀₀₀), (¹¹¹₁₁₁)

What’s wrong??

Languages of encodings should be closed under padding with 0’s After complement, keep only final states that are stable under 0.

Example of translation

Consider the (unsatisfiable) formula

ψ = ∃x .¬∃y . (y =x +1) ψ = ∃x . ¬∃y . (y =x+1) ψ = ∃x .¬∃y . (y =x+1)

1 Start from automaton A_{y=x+1yy=x+1=x+1}

2 Project away the encoding of yyy, thus capturing∃y .∃y .∃y .(y(y(y ===xxx+++1)1)1)

3 Complement the det. automaton, thus capturing ¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

4 Project away the encoding of xxx, thus getting ∃x .∃x .∃x .¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

p q

(¹¹¹

0 00)

(⁰⁰⁰

111)

(⁰⁰⁰₀₀₀), (¹¹¹₁₁₁)

What’s wrong??

Languages of encodings should be closed under padding with 0’s After complement, keep only final states that are stable under 0.

Example of translation

Consider the (unsatisfiable) formula

ψ = ∃x .¬∃y . (y =x +1) ψ = ∃x . ¬∃y . (y =x+1) ψ = ∃x .¬∃y . (y =x+1)

1 Start from automaton A_{y=x+1yy=x+1=x+1}

2 Project away the encoding of yyy, thus capturing∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

3 Complement the det. automaton, thus capturing ¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

4 Project away the encoding of xxx, thus getting ∃x .∃x .∃x .¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

p q

(¹¹¹

0 00

×⁾

(⁰⁰⁰

111

×⁾

(⁰⁰⁰₀₀₀

×^{), (}

1 1 1 1 1

×1⁾

What’s wrong??

Languages of encodings should be closed under padding with 0’s After complement, keep only final states that are stable under 0.

Example of translation

Consider the (unsatisfiable) formula

ψ = ∃x .¬∃y . (y =x +1) ψ = ∃x . ¬∃y . (y =x+1) ψ = ∃x .¬∃y . (y =x+1)

1 Start from automaton A_{y=x+1yy=x+1=x+1}

2 Project away the encoding of yyy, thus capturing∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

3 Complement the det. automaton, thus capturing ¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

4 Project away the encoding of xxx, thus getting ∃x .∃x .∃x .¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

p q

(¹₀¹¹₀₀

×⁾

(⁰⁰⁰

111

×⁾

(⁰⁰⁰

0 0 0

×^{), (}

11 1 1 1 1

×⁾

What’s wrong??

Languages of encodings should be closed under padding with 0’s After complement, keep only final states that are stable under 0.

Example of translation

Consider the (unsatisfiable) formula

ψ = ∃x .¬∃y . (y =x +1) ψ = ∃x . ¬∃y . (y =x+1) ψ = ∃x .¬∃y . (y =x+1)

1 Start from automaton A_{y=x+1yy=x+1=x+1}

2 Project away the encoding of yyy, thus capturing∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

3 Complement the det. automaton, thus capturing ¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

4 Project away the encoding of xxx, thus getting ∃x .∃x .∃x .¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

p q

(×¹¹¹

000

×⁾

(×⁰⁰⁰

111

×⁾

(×⁰⁰⁰

0 0 0

×^{), (}

11 1

×

1 1 1

×⁾

What’s wrong??

Languages of encodings should be closed under padding with 0’s After complement, keep only final states that are stable under 0.

Example of translation

Consider the (unsatisfiable) formula

ψ = ∃x .¬∃y . (y =x +1) ψ = ∃x . ¬∃y . (y =x+1) ψ = ∃x .¬∃y . (y =x+1)

1 Start from automaton A_{y=x+1yy=x+1=x+1}

2 Project away the encoding of yyy, thus capturing∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

3 Complement the det. automaton, thus capturing ¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

4 Project away the encoding of xxx, thus getting ∃x .∃x .∃x .¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

p q

(×¹¹¹

000

×⁾

(×⁰⁰⁰

111

×⁾

(×⁰⁰⁰

0 0 0

×^{), (}

11 1

×

1 1 1

×⁾

What’s wrong??

Languages of encodings should be closed under padding with 0’s After complement, keep only final states that are stable under 0.

Example of translation

Consider the (unsatisfiable) formula

ψ = ∃x .¬∃y . (y =x +1) ψ = ∃x . ¬∃y . (y =x+1) ψ = ∃x .¬∃y . (y =x+1)

1 Start from automaton A_{y=x+1yy=x+1=x+1}

2 Project away the encoding of yyy, thus capturing∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

3 Complement the det. automaton, thus capturing ¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

4 Project away the encoding of xxx, thus getting ∃x .∃x .∃x .¬¬¬∃y .∃y .∃y . (y(y(y ===xxx+++1)1)1)

p q

(×¹¹¹

000

×⁾

(×⁰⁰⁰

111

×⁾

(×⁰⁰⁰

0 0 0

×^{), (}

11 1

×

1 1 1

×⁾

What’s wrong??

Languages of encodings should be closed under padding with 0’s After complement, keep only final states that are stable under 0.

The previous result can be generalized to many other structures:

Definition

An automatic structure is a structure that is isomorphic to (L, R₁, . . . , R_n)

where

L is a regular language of words over Σ

(each word identifies a precise element of the structure) each relation R_i has arity k_i and is represented

by a regular language L_i over (Σ ⊎ {#})^ki (e.g. (ab,abb) ∈R_i iff (^a_a)(^b_b)(^#

b) ∈L_i )

Examples of automatic structures (N, +, ∣^p)

(N, +, ∣^p)

(N, +, ∣^p), with x ∣p y iff x = pⁿ divides y

Binary tree with successor, ancestor, and equi-level predicates Unlabelled grid (N × N, →, ↓)((N × N, →, ↓)N × N, →, ↓)

The previous result can be generalized to many other structures:

Definition

An automatic structure is a structure that is isomorphic to (L, R₁, . . . , R_n)

where

L is a regular language of words over Σ

(each word identifies a precise element of the structure) each relation R_i has arity k_i and is represented

by a regular language L_i over (Σ ⊎ {#})^ki (e.g. (ab,abb) ∈R_i iff (^a_a)(^b_b)(^#

b) ∈L_i ) Examples of automatic structures

(N, +, ∣^p) (N, +, ∣^p)

(N, +, ∣^p), with x ∣p y iff x = pⁿ divides y

Binary tree with successor, ancestor, and equi-level predicates Unlabelled grid (N × N, →, ↓)((N × N, →, ↓)N × N, →, ↓)

Theorem (B¨uchi ’60, Hodgson ’76, Khoussainov & Nerode ’94) Every automatic structure has a decidable first-order theory.

On the other hand...

Theorem

Some automatic structures have an undecidable reachability problem.

The transition graphtransition graphtransition graph of a Turing machine is automatic! configurations are encoded by words aaa111...a...a...ai −1i −1i −1qqqaaaiiiaaai +1i +1i +1...a...a...annn

transitions are of the following forms

a₁...a_{i −1}qqqaaa_iiia_{i +1}...a_n a₁...a_{i −1}qqqaaa_iiia_{i +1}...a_n a₁...a_{i −1}aaa_iiiqqqa_{i +1}...a_n

↓

↓↓ ↓↓↓ ↓↓↓

a₁...a_{i −1}qqq^′′′aaa_i^′_i^′_i^′a_{i +1}...a_n a₁...a_{i −1}aaa_i^′_i^′′_iqqq^′′′a_{i +1}...a_n a₁...a_{i −1}qqq^′′′aaa_iii^′′′a_{i +1}...a_n

Theorem (B¨uchi ’60, Hodgson ’76, Khoussainov & Nerode ’94) Every automatic structure has a decidable first-order theory.

On the other hand...

Theorem

Some automatic structures have an undecidable reachability problem.

The transition graphtransition graphtransition graph of a Turing machine is automatic!

configurations are encoded by words aaa111...a...a...a_{i −1}i −1_{i −1}qqqaaa_ii_iaaa_{i +1}i +1_{i +1}...a...a...annn

transitions are of the following forms

a1...ai −1qqqaaai_iiai +1...an a1...ai −1qqqaaaii_iai +1...an a1...ai −1aaai_iiqqqai +1...an

↓

↓↓ ↓↓↓ ↓↓↓

a₁...a_{i −1}qqq^′′′aaa_i^′_i^′_i^′a_{i +1}...a_n a₁...a_{i −1}aaa_i^′_i^′′_iqqq^′′′a_{i +1}...a_n a₁...a_{i −1}qqq^′′′aaa^′_iii^′′a_{i +1}...a_n

Next