The transformational approach Gabriele Puppis

(1)

The transformational approach

Gabriele Puppis

LaBRI / CNRS

(2)

MSO-interpretation as a graph transformation

1 Start from a graph G (e.g. the binary tree) that has a decidable MSO-theory

2 Transform G into a new graph G^′

by logically defining nodes and edges of G^′ inside G

3 Given any MSO property ψ over G^′,

decide it by rephrasing it into a property over G

(3)

Definition

An MSO-interpretation is a tuple I of formulas ϕ

iii

dom(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¶

domain formula

ϕ

i , j i , j i , j

e₁(x , y ) . . . ϕ

i , j i , ji , j

e_k(x , y )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

edge formulas

ϕ

iii

a₁(x ) . . . ϕ

iii

a_m(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

color formulas

defining a transformation from graph G to graph I(G ) such that

(i ,

v

)

is a vertex of I(G ) iff (G , v ) ⊧ ϕ

iii

dom(x ) (u, v ) is an e-edge of I(G )

((i ,u),(j ,v))is an e-edge of I(G )

iff (G , u, v ) ⊧ ϕ

i , j i , ji , j

e(x , y )

(i ,

v

)

has color a in I(G ) iff (G , v ) ⊧ ϕ

iii

a(x )

Transfer theorem

Every sentence ψ can be transformed into I⁻¹(ψ) such that I (G ) ⊧ ψ

I (G ) ⊧ ψ

I (G ) ⊧ ψ iff G ⊧ IG ⊧ IG ⊧ I⁻¹⁻¹⁻¹(ψ)(ψ)(ψ)

Hence, if G has decidable MSO theory, then so has I(G ).

(4)

Definition

iii

dom(x ) ϕ

iii

dom(x ) ϕ

iii

dom(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¶

domain formula

ϕ

i , j i , j i , j

e₁(x , y ) . . . ϕ

i , j i , ji , j

e_k(x , y )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

edge formulas

ϕ

iii

a₁(x ) . . . ϕ

iii

a_m(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

color formulas

(i ,

v

)

iii

dom(x )

(i ,

v

)

iii

dom(x )

(i ,

v

)

iii

iff (G , u, v ) ⊧ ϕ

i , j i , ji , j

e(x , y )

(i ,

v

)

iii

a(x )

Transfer theorem

I (G ) ⊧ ψ

(5)

Definition

iii

dom(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¶

domain formula

ϕ

i , j i , j i , j

e₁(x , y ) . . . ϕ

i , j i , j i , j

e_k(x , y ) ϕ

i , j i , ji , j

e₁(x , y ) . . . ϕ

i , j i , j i , j

e_k(x , y ) ϕ

i , j i , j i , j

e₁(x , y ) . . . ϕ

i , j i , ji , j

e_k(x , y )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

edge formulas

ϕ

iii

a₁(x ) . . . ϕ

iii

a_m(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

color formulas

(i ,

v

)

iii

((i , u), (j , v )) is an e-edge of I(G )

iff (G , u, v ) ⊧ ϕ

i , j i , j i , j

e(x , y ) (u, v ) is an e-edge of I(G )

iff (G , u, v ) ⊧ ϕ

i , j i , j i , j

e(x , y ) (u, v ) is an e-edge of I(G )

iff (G , u, v ) ⊧ ϕ

i , j i , ji , j

e(x , y )

(i ,

v

)

iii

a(x )

Transfer theorem

I (G ) ⊧ ψ

(6)

Definition

iii

dom(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¶

domain formula

ϕ

i , j i , j i , j

e₁(x , y ) . . . ϕ

i , j i , ji , j

e_k(x , y )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

edge formulas

ϕ

iii

a₁(x ) . . . ϕ

iii

a_m(x ) ϕ

iii

a₁(x ) . . . ϕ

iii

am(x ) ϕ

iii

a₁(x ) . . . ϕ

iii

a_m(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

color formulas

(i ,

v

)

iii

iff (G , u, v ) ⊧ ϕ

i , j i , ji , j

e(x , y )

(i ,

v

)

iii

a(x )

(i ,

v

)

iii

a(x )

(i ,

v

)

iii

a(x )

Transfer theorem

I (G ) ⊧ ψ

(7)

Definition

iii

dom(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¶

domain formula

ϕ

i , j i , j i , j

e₁(x , y ) . . . ϕ

i , j i , ji , j

e_k(x , y )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

edge formulas

ϕ

iii

a₁(x ) . . . ϕ

iii

a_m(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

color formulas

(i ,

v

)

iii

iff (G , u, v ) ⊧ ϕ

i , j i , ji , j

e(x , y )

(i ,

v

)

iii

a(x ) Transfer theorem

I (G ) ⊧ ψ

(8)

Definition

An MSO-/////////////////interpretation transduction is a tuple I of formulas ϕⁱⁱⁱdom(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¶

domain formula

ϕe^{i , j}^{i , j}^{i , j}₁(x , y ) . . . ϕe^{i , j}^{i , j}^{i , j}_k(x , y )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

edge formulas

ϕaⁱⁱⁱ₁(x ) . . . ϕⁱⁱⁱa_m(x )

´ ¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¸¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¹¶

color formulas

defining a transformation from graph G to graph I(G ) such that (i ,v)is a vertex of I(G ) iff (G , v ) ⊧ ϕⁱⁱⁱ_dom(x )

(u, v ) is an e-edge of I(G )

((i ,u),(j ,v))is an e-edge of I(G ) iff (G , u, v ) ⊧ ϕe^{i , j}^{i , j}^{i , j}(x , y ) (i ,v)has color a in I(G ) iff (G , v ) ⊧ ϕaⁱⁱⁱ(x ) Transfer theorem

I (G ) ⊧ ψ

(9)

Most edge formulas can be abbreviated by regular expressions:

“aaa” abbreviates (x , y ) ∈ E(x , y ) ∈ E(x , y ) ∈ E_a_a_a

“¯a¯a¯a” abbreviates (y , x ) ∈ E(y , x ) ∈ E(y , x ) ∈ E_aa_a

“a + ba + b” abbreviates (x , y ) ∈ Ea + b (x , y ) ∈ E(x , y ) ∈ Ea_aa ∨∨∨ (x , y ) ∈ E(x , y ) ∈ E(x , y ) ∈ Eb_bb

“a ⋅ ba ⋅ b” abbreviates ∃z . (x , z ) ∈ Ea ⋅ b ∃z . (x , z ) ∈ E∃z . (x , z ) ∈ E_a_a_a ∧∧∧ (z , y ) ∈ E(z , y ) ∈ E(z , y ) ∈ E_b_b_b

“aaa^⋆^⋆^⋆” abbreviates (x , y ) ∈ E(x , y ) ∈ E(x , y ) ∈ E_a_a_a^⋆^⋆^⋆

“ccc ” abbreviates c (x )c (x )c (x ) (assume vertex colors ≠ edge labels)

Example

The regular expression “aaa^⋆^⋆^⋆⋅ (c + d ) ⋅ ¯⋅ (c + d ) ⋅ ¯⋅ (c + d ) ⋅ ¯bbb” describes a formula ϕ(x , y ) that witnesses a path from x to y such that

1 traverses a sequence of a-labelled edges

2 reaches a vertex with color c or d

3 finally traverses in backward direction a b-labelled edge

(10)

“ccc ” abbreviates c (x )c (x )c (x ) (assume vertex colors ≠ edge labels) Example

(11)

“ccc ” abbreviates c (x )c (x )c (x ) (assume vertex colors ≠ edge labels) Example

(12)

Special forms of interpretations on trees

A rational restriction is an MSO-interpretation of tree defined by ϕ_dom(x ) = “ ∃ path π from root to x such that π ∈ L ”“ ∃ path π from root to x such that π ∈ L ”“ ∃ path π from root to x such that π ∈ L ” Similarly, an inverse rational mapping is defined as

ϕe(x , y ) = “ ∃ path π from x to y such that π ∈ L“ ∃ path π from x to y such that π ∈ L“ ∃ path π from x to y such that π ∈ Le_ee”””

xxx yyy

e π ∈ Le

(13)

Definition

A pushdown system is a tuple P = (Q, Σ, Γ, ∆), where Q is a finite set of control states

Σ is a finite alphabet for transition labels Γ is a finite alphabet for stack symbols

∆ ⊆ Q × Γ × Σ × Q × Γ^⋆ is a finite set of transition rules

Configurations = pairs (q

®

state

,w

®

stack

) ∈ Q×Γ^⋆

Transitions = (q,γw) ÐÐÐ^a→ (q^′,vw) iff (q,γ, a,q^′,v

®∈ Γ^≤2

) ∈∆

W.l.o.g. assume that stack length changes at most by 1

(14)

Definition

∆ ⊆ Q × Γ × Σ × Q × Γ^⋆ is a finite set of transition rules Configurations = pairs (q

®

state

,w

®

stack

) ∈ Q×Γ^⋆

®∈ Γ^≤2

) ∈∆

(15)

Definition

∆ ⊆ Q × Γ × Σ × Q × Γ^⋆ is a finite set of transition rules Configurations = pairs (q

®

state

,w

®

stack

) ∈ Q×Γ^⋆

®∈ Γ^≤2

) ∈∆

(16)

Interest in properties of transition graphs of pushdown systems Context-free graph

A connected component of a graph is a maximal subgraph in which every two vertices can be connected by a path that traverses edges in either direction.

A context-free graph is a connected component of the transition graph of a pushdown system.

Example

q₁ ^{γ, c} q₂ γ, a ∶ push γ

γ, b ∶ pop γ γ, d ∶ pop γ

q1ε q1γ q1γγ . . .

q₂ε q₂γ q₁γγ . . .

b

a

b

a

c c b

d d

d

(17)

Theorem (Caucal ’96)

Context-free graphs are definable in the binary tree using rational restrictions and inverse finite mappings.

Proof sketch in the next slide...

Corollary (Muller & Schupp ’85)

MSO is decidable over context-free graphs.

(18)

Context-free graphs are definable by restrictions and inverse mappings.

Consider a pushdown system P = (Q, Σ, Γ, ∆) and theQQQ⊎⊎⊎ΓΓΓ-labelled tree (interpretable in the binary tree)

configurations of P: ϕdom(x ) = ∃ πroot,x ∈ΓΓΓ^⋆^⋆^⋆⋅⋅⋅QQQ

transitions of P: ϕ_a(x , y ) = ∃ π_{x ,y} ∈

∪

_(q,γ,a,q^′_,v)∈∆(¯q ⋅ ¯¯¯q ⋅ ¯q ⋅ ¯γ ⋅ vγ ⋅ vγ ⋅ v^rev^rev^rev⋅⋅⋅qqq^′^′^′) connected component...

⋮ ⋮

⋮ ⋮ ⋮ ⋮

⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

γ

q

(19)

configurations of P: ϕ_dom(x ) = ∃ πroot,x ∈ΓΓΓ^⋆^⋆^⋆⋅⋅⋅QQQ

∪

⋮ ⋮

⋮ ⋮ ⋮ ⋮

⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

γ

q

(20)

∪

_(q,γ,a,q^′_,v)∈∆(¯q ⋅ ¯¯¯q ⋅ ¯q ⋅ ¯γ ⋅ vγ ⋅ vγ ⋅ v^rev^rev^rev⋅⋅⋅qqq^′^′^′)

connected component...

⋮ ⋮

⋮ ⋮ ⋮ ⋮

⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

γ

q

(21)

∪

⋮ ⋮

⋮ ⋮ ⋮ ⋮

⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮

γ

q

(22)

The previous result can be lifted to prefix-rewriting systems, which generalize pushdown systems by giving graphs with infinite degree:

no distinction between control states and stack letters (a single alphabet is used)

less restricted forms of rewriting rules

(more than one letter can be rewritten in a single transition)

Definition

A prefix-rewriting system is a tuple P = (Σ, Γ, ∆), where Σ is a finite alphabet for transition labels

Γ is a finite alphabet for “stack” symbols

∆ is a finite set of transition rules of the form (U, a, V )(U, a, V )(U, a, V ), with a ∈ Σ and U, V regular languages over ΓU, V regular languages over ΓU, V regular languages over Γ.

Configurations = words in Γ^⋆ (or in some regular language) Transitions = u wu wu w ÐÐÐÐÐÐÐâÐââÐ→→→ v wv wv w

iff u ∈ Uu ∈ Uu ∈ U and v ∈ Vv ∈ Vv ∈ V for some (U, a, V ) ∈ ∆((U, a, V ) ∈ ∆U, a, V ) ∈ ∆

(23)

(more than one letter can be rewritten in a single transition) Definition

Configurations = words in Γ^⋆ (or in some regular language) Transitions = u wu wu w ÐÐÐÐÐÐÐâÐââÐ→→→ v wv wv w

(24)

(more than one letter can be rewritten in a single transition) Definition

Configurations = words in Γ^⋆ (or in some regular language) Transitions = u wu wu w ÐÐÐÐÐÐÐâÐÐââ→→→ v wv wv w

(25)

Definition

A prefix-recognizable graph is

the transition graph of a prefix-rewriting system.

Example

Consider the prefix rewriting system P = (Σ, Γ, ∆), where Σ = {succsuccsucc,smallersmallersmaller}

Γ = {γ}

∆ consists of the two rules

({ε},succsuccsucc, {γ}) and ({γ}⁺,smallersmallersmaller, {ε})

ε γ γ² γ³ γ⁴ . . .

(26)

Prefix-recognizable graphs are definable in the binary tree using rational restrictions and inverse rational mappings.

Exactly the same proof as before...

u w ÐÐâÐ→ v w u w ÐÐâÐ→ v w u w ÐÐâÐ→ v w

iff u ∈ U

u ∈ Uu ∈ U and v ∈ Vv ∈ Vv ∈ V for some (U, a, V ) ∈ ∆

(27)

iff u ∈ U

xx x

¯ u¯

u¯u

¯w¯w¯w

(28)

iff u ∈ U

xx x

¯ u¯

u¯u

¯w¯w¯w

y y y vrev

vrev

w

rev

w

rev

w

rev

(29)

iff u ∈ U

xx x

¯ u¯

u¯u

¯w¯w¯w

y y y vrev

vrev

w

rev

w

rev

w

rev

a

ϕ_a =

∪

_{(U,a,V )∈∆}U ⋅ V^rev ϕ_a =

∪

_{(U,a,V )∈∆}U ⋅ V^rev ϕ_a =

∪

_{(U,a,V )∈∆}U ⋅ V^rev

(30)

We just saw that

context-free graphs can be defined in the binary tree using rational restrictions and inverse finite mappings

prefix-recognizable graphs can be defined in the binary tree using rational restrictions and inverse rational mappings

The converse is also true:

The graphs that can be defined in the binary tree using rational restrictions and inverse finite / rational mappings are context-free / prefix-recognizable.

(31)

We just saw that

context-free graphs can be defined in the binary tree using rational restrictions and inverse finite mappings

prefix-recognizable graphs can be defined in the binary tree using rational restrictions and inverse rational mappings

The converse is also true:

The graphs that can be defined in the binary tree using rational restrictions and inverse finite / rational mappings are context-free / prefix-recognizable.

(32)

Context-free graphs have alternative representations based on hyperedge-replacement

Example of hyperedge replacement G ∶

h h h

H ∶ 1 1 1

2 2 2

3 3 3

G [h/H] ∶

(33)

h h h

H ∶ 1 1 1

2 2 2

3 3 3

G [h/H] ∶

(34)

h h h

H ∶ 1 1 1

2 2 2

3 3 3

G [h/H] ∶

(35)

Some definitions

A hyperedge is a sequence of vertices h = (v1, . . . , v_k)

A hypergraph is a structure of vertices and hyperedges (different hyperedges are given different labels).

A hyperedge replacement is the replacement of a hyperedge h = (v1, ..., vk) in a hypergraph G with another hypergraph H (glueing points are represented by marking vertices of H) A hyperedge replacement grammar is

a finite set of rewriting rules of the form h₁↦H₁ . . . h_n↦H_n together with an initial hyperedge h₁.

Finally, one defines the limit of a series of replacements h₁ ↦ H₁ ↦ H₁[h_i₂/H₂] ↦ . . . Since hyperedge replacements are confluent,

the limit is the same for all (fair) series of replacements!

(36)

Some definitions

A hyperedge is a sequence of vertices h = (v1, . . . , v_k) A hypergraph is a structure of vertices and hyperedges (different hyperedges are given different labels).

(37)

Some definitions

A hyperedge replacement is the replacement of a hyperedge h = (v1, ..., vk) in a hypergraph G with another hypergraph H (glueing points are represented by marking vertices of H)

A hyperedge replacement grammar is a finite set of rewriting rules of the form

h₁↦H₁ . . . h_n↦H_n together with an initial hyperedge h₁.

(38)

Some definitions

(39)

Some definitions

(40)

Limit graph of a hyperedge replacement grammar

h1

hh11

↦

H1∶ 1 1

1 222

hh1

h1 1

Limit graphs can be disconnecteddisconnecteddisconnected and have unbounded degreeunbounded degreeunbounded degree

(41)

h1

hh11

↦

H1∶ 1 1

1 222

hh1

h1 1

h₁ h₁ h₁

(42)

h1

hh11

↦

H1∶ 1 1

1 222

hh1

h1 1

hhh111

(43)

h1

hh11

↦

H1∶ 1 1

1 222

hh1

h1 1

h₁ h1

h₁

(44)

h1

hh11

↦

H1∶ 1 1

1 222

hh1

h1 1

. . .

(45)

If we restrict ourselves to special forms of grammars, where there are no markings on hyperedges

there are no repetitions of vertices in hyperedges vertices of hyperedges have incident terminal edges . . .

Then:

Theorem (Muller & Schupp ’85)

The context-free graphs are the limit graphs of

special forms of hyperedge-replacement graph grammars.

(46)

Proof idea in one direction: consider end-components Vn = {v ∣ dist(v , V0) ≥n }

V_n = {v ∣ dist(v , V₀) ≥n } Vn = {v ∣ dist(v , V0) ≥n }

. . .

. . . . . .

. . . b

d

a

b

d c

a

b

d c

a

b

d c

Only finitely many non-isomorphic end-components, each one inducing a hyperedge replacement rule:

h₁

↦

b

h₂ d

h₂

↦

^c

a

b h₂

d

(47)

. . .

. . . . . .

. . . b

d

a

b

d c

a

b

d c

a

b

d c

h₁

↦

b

h₂ d

h₂

↦

^c

a

b h₂

d

(48)

. . .

. . . . . .

. . . b

d

a

b

d c

a

b

d c

a

b

d c

h₁

↦

b

h₂ d

h₂

↦

^c

a

b h₂

d

(49)

. . .

. . . . . .

. . . b

d

a

b

d c

a

b

d c

a

b

d c

h₁

↦

b

h₂ d

h₂

↦

^c

a

b h₂

d

(50)

. . .

. . . b

d

a

b

d c

a

b

d c

a

b

d c

h₁

↦

b

h₂ d

h₂

↦

^c

a

b h₂

d

(51)

. . .

. . . b

d

a

b

d c

a

b

d c

a

b

d c

h₁

↦

b

h₂ d

h₂

↦

^c

a

b h₂

d

(52)

Analogous results hold for prefix-recognizable graphs:

Theorem (Courcelle ’92)

The prefix-recognizable graphs are the limit graphs of vertex-replacement graph grammars.

Operations underlying vertex-replacement grammars:

Disjoint union: G ⊎ G^′ Vertex relabelling: G [a/b]

Edge creation: G [a → b]

(53)

Transfer theorems can be proved for other transformations besides MSO-interpretations and MSO-transductions, e.g. for unfoldings...

Definition

The unfolding of a rooted graph G is the tree unf(G )unf(G )unf(G ), where vertices are the finite pathsfinite pathsfinite paths in G originating from the root edges are given by path-extensionpath-extensionpath-extension relation

i.e. (π, π^′) is an a-labelled edge in unf(G ) iff

π^′ is the extension of π with an a-labelled edge in G

Transfer theorem (Muchnik ’84, Courcelle ’96, Walukiewicz ’02, ...) Every sentence ψ can be transformed into unf⁻¹(ψ) such that

unf(G ) ⊧ ψ unf(G ) ⊧ ψ

unf(G ) ⊧ ψ iff G ⊧ unfG ⊧ unfG ⊧ unf⁻¹⁻¹⁻¹(ψ)(ψ)(ψ)

Next slide shows why this subsumes B¨uchi and Rabin’s theorems...

(54)

Definition

(55)

Definition

(56)

Examples of unfoldings

. . .

(57)

. . .

(58)

. . .

(59)

. . .

(60)

Application example

Consider a context-free graph, which has decidable MSO theory.

1 First apply unfoldingunfoldingunfolding: this gives a tree with decidable MSO theory

2 Then apply MSO-interpretationMSO-interpretationMSO-interpretation: this gives (N, +1, Powers)

0 1

2 3

4 5 6 7

8 9 10 11 12 13 14 15

(61)

Application example

0 1

2 3

4 5 6 7

8 9 10 11 12 13 14 15

(62)

Application example

0 1

2 3

4 5 6 7

8 9 10 11 12 13 14 15

(63)

Higher-order definable words (e.g. see Fratani & Senizergues ’06)

(N, +1, {222ⁿⁿⁿ∣n ∈ N}) (N, +1, {2²

2²nⁿ

2²ⁿ ∣n ∈ N})

(N, +1, {22 ⋱ ⋱ ²

2

2 ⋱

2}n times

∣n ∈ N}) (but MSO is still decidable)

(N, +1, {⌊n

√n⌋

⌊n√ n⌋

⌊n√

n⌋ ∣ n ∈ N})

(N, +1, {⌊n log n⌋⌊n log n⌋⌊n log n⌋ ∣ n ∈ N})

(N, +1, {nnn²²²∣n ∈ N}, {nnn⁶⁶⁶∣n ∈ N}, {nnn³⁰³⁰³⁰∣n ∈ N}, . . . )

(N, +1, {nnn²²²∣n ∈ N}, {nnn³³³∣n ∈ N}) (is MSO decidable?)

(64)

Higher-order definable words (e.g. see Fratani & Senizergues ’06)

(N, +1, {222ⁿⁿⁿ∣n ∈ N}) (N, +1, {2²

2²nⁿ

2²ⁿ ∣n ∈ N})

(N, +1, {22 ⋱ ⋱ ²

2

2 ⋱

2}n times

∣n ∈ N}) (but MSO is still decidable)

(N, +1, {⌊n

√n⌋

⌊n√ n⌋

⌊n√

n⌋ ∣ n ∈ N})

(N, +1, {⌊n log n⌋⌊n log n⌋⌊n log n⌋ ∣ n ∈ N})

(N, +1, {nnn²²²∣n ∈ N}, {nnn⁶⁶⁶∣n ∈ N}, {nnn³⁰³⁰³⁰∣n ∈ N}, . . . )

(N, +1, {nnn²²²∣n ∈ N}, {nnn³³³∣n ∈ N}) (is MSO decidable?)

(65)

Since interpretation and unfolding preserve decidability of MSO theories we can iterate these two operations and produce new graphs...

Definition

The Caucal hierarchy is a series of inductively defined graphs and trees:

GraphsGraphsGraphs₀₀₀ = {finite graphs } Trees_n

Trees_n

Trees_n = { unf(G ) ∣ G ∈ Graphs_n} Graphs_n+1

Graphs_n+1

Graphs_n+1 = { I (T ) ∣ I interpretation, T ∈ Treesn}

Examples

Trees0= {regular trees }, Graphs₁= {prefix-recognizable graphs }, . . .

Graphs and trees of Caucal hierarchy have decidable MSO theories.

(66)

Definition

Trees_n

Graphs_n+1

Examples

(67)

Definition

Trees_n

Graphs_n+1

Examples

(68)

Theorem (Carayol & W¨ohrle ’03)

The graphs in level n of Caucal hierarchylevel n of Caucal hierarchylevel n of Caucal hierarchy are ε-closures of transition graphs of order-n-n-n pushdown systems.

a ∶ push γ

b ∶ pop γ γγ γ c∶push

2

d∶pop

2

γ γγ γγγ a ∶ push γ

b ∶ pop γ γ

γγ

ε ∶ push γ^′

ε ∶ pop γ^′

γγγ γγγ γ^′ γγ^′^′

(69)

a ∶ push γ

b ∶ pop γ γγ γ

c∶push

2

d∶pop

2

γ γγ γγγ a ∶ push γ

b ∶ pop γ γ

γγ

ε ∶ push γ^′

ε ∶ pop γ^′

(70)

a ∶ push γ

2

d∶pop

2

γγγ γγγ

a ∶ push γ

b ∶ pop γ γ

γγ

ε ∶ push γ^′

ε ∶ pop γ^′

(71)

a ∶ push γ

2

d∶pop

2

γγγ γγγ a ∶ push γ

b ∶ pop γ γγγ

ε ∶ push γ^′

ε ∶ pop γ^′

(72)

Another example of application of unfolding

Consider the operation of substitution of variables by terms:

θx

θx(g, h) ↦ g[x/h]

f

θx c

g h

a x b

↦

f

g c

a h

b

= unf unf unf

⎛

⎜

⎜⎜

⎜

⎜⎜

⎝

⎞

⎟

⎟⎟

⎟

⎟⎟

⎠

f

θx c

g h

a x b

Theorem (Courcelle & Knapik ’02)

The operation of substitution of (a fixed number of) variables by terms preserves decidability of MSO theories.

(73)

θx

f

θ_x ^c

g h

a x b

↦

f

g c

a h

b

= unf unf unf

⎛

⎜

⎜⎜

⎜

⎜⎜

⎝

⎞

⎟

⎟⎟

⎟

⎟⎟

⎠

f

θx c

g h

a x b

(74)

θx

f

θ_x ^c

g h

a x b

↦

f

g c

a h

b

= unf unf unf

⎛

⎜

⎜⎜

⎜

⎜⎜

⎝

⎞

⎟

⎟⎟

⎟

⎟⎟

⎠

f

θ_x ^c

g h

a x b

(75)

θx

f

θ_x ^c

g h

a x b

↦

f

g c

a h

b

= unf unf unf

⎛

⎜

⎜⎜

⎜

⎜⎜

⎝

⎞

⎟

⎟⎟

⎟

⎟⎟

⎠

f

θ_x ^c

g h

a x b

(76)

θx

f

θ_x ^c

g h

a x b

↦

f

g c

a h

b

= unf unf unf

⎛

⎜

⎜⎜

⎜

⎜⎜

⎝

⎞

⎟

⎟⎟

⎟

⎟⎟

⎠

f

θ_x ^c

g h

a x b

(77)

It is convenient to see substitution as a form of β-reduction in λ-calculus

β-reduction in λ-calculusβ-reduction in λ-calculus, but without variable renaming:

(λx . g(a, x )) @ h(b) ↦ g(a, x ) [x /h(b)]

Theorem (Knapik & Niwi´nski & Urzyczyn ’02)

In the safe fragment of typed λ-calculus, β-reduction can be performed without variable renaming, that is, by substitution.

Corollary

In the safe typed λ-calculus, simultaneous β-reduction of redexes can be implemented by MSO-interpretationMSO-interpretationMSO-interpretation followed by unfoldingunfoldingunfolding.

The above result applies also to infinitary terms!

(78)

It is convenient to see substitution as a form of β-reduction in λ-calculus

β-reduction in λ-calculusβ-reduction in λ-calculus, but without variable renaming:

(λx . g(a, x )) @ h(b) ↦ g(a, x ) [x /h(b)]

Theorem (Knapik & Niwi´nski & Urzyczyn ’02)

In the safe fragment of typed λ-calculus, β-reduction can be performed without variable renaming, that is, by substitution.

Corollary

In the safe typed λ-calculus, simultaneous β-reduction of redexes can be implemented by MSO-interpretationMSO-interpretationMSO-interpretation followed by unfoldingunfoldingunfolding.

The above result applies also to infinitary terms!