Multi-ReturnMacro Tree Transducers
CIAA 2008, San Francisco

Kazuhiro Inaba
The Univ. of Tokyo Haruo Hosoya
NICTA, and UNSW Sebastian Maneth
The Univ. of Tokyo

Tree to Tree Translations
 Applications

 Models Compiler Natural Language

Processing
 XML Query/Translation
 XSLT, XQuery, XDuce, …

…

 Tree Transducer
 Top-down / bottom-up
 with/without lookahead …
 Attributed Tree Transducer
 MSO Tree Translation
 Pebble Tree Transducer
 Macro Tree Transducer
…
 Multi-Return Macro TreeTransducer

Models of Tree Translation
 Top-down Tree Transducer[Rounds 70, Thatcher 70]

 Finite-state translation defined by structural(mutual) recursion on the input tree<q, bin(x1,x2)><q, leaf>→ fst( <q,x1>, <p,x2> )→ leaf<p, bin(x1,x2)><p, leaf>→ snd( <q,x1>, <p,x2> )→ leaf

fst

bin
bin

bin
leaf

leaf

fst

bin

leaf

leaf

leaf

fst
leaf

leaf

leaf

<q, bin(x1,x2)><q, leaf>→ fst( <q,x1>, <p,x2> )→ leaf<p, bin(x1,x2)><p, leaf>→ snd( <q,x1>, <p,x2> )→ leafsndleafleafModels of Tree Translation
 Macro Tree Transducer (MTT)[Engelfriet 80, Courcell&Franchi-Zannettacci 82]

 Tree Transducer + Context parameters Strictly more expressive than tree transducers<q, bin(x1,x2)>→ bin( <p,x1>(leaf),<p,x2>(leaf) )<p, bin(x1,x2)>(y) → bin( <p,x1>(1(y)),<p,x2>(2(y)) )<p, leaf>(y)→ ybin
bin

bin
leaf

leaf

bin
bin

leaf

leaf

<q, bin(x1,x2)>

bin

leaf

bin
12

11

11

leaf

leaf

bin

2

12

122

leaf

leaf

leaf

→ bin( <p,x1>(leaf),<p,x2>(leaf) )<p, bin(x1,x2)>(y1)→bin( <p,x1>(1(y1)),<p,x2>(2(y1)) )<p, leaf>(y1)→ y1Today‟s Topic Multi-Return Macro Tree Transducer[Inaba, Hosoya, and Maneth 08]

 Macro Tree Transducer + Multiple return trees<q, bin(x1,x2)>(y1) →<q, leaf>(y1)→<p, bin(x1,x2)>(y1) →<p, leaf>(y1)→let (z1,z2) = <q,x1>(1(y1)) inlet (z3,z4) = <p,x2>(2(y1)) in(bin(z1,z3), fst(z2,z4))(leaf, y1)
let (z1,z2) = <q,x1>(1(y1)) inlet (z3,z4) = <p,x2>(2(y1)) in(bin(z1,z3), snd(z2,z4))(leaf, y1)

Outline of the Talk Overview
 Definitions of MTTs and mr-MTTs
 Properties of mr-MTTs
 Expressiveness Closure under DtT composition

 Characterization of mr-MTTs

Definition ofMacro Tree Transducers (MTTs)
 A MTT is a tuple M = (Q, Σ, Δ, q0, R) where Q : Ranked set of states (rank = # of parameters) Σ : Ranked set of input alphabet
 Δ : Ranked set of output alphabet q0 : Initial state of rank-0
 R : Set of rules of the following form:<q, σ(x1,…,xk)>(y1, …, ym) → RHS
RHS ::= δ( RHS, …, RHS )| <q’, xi>( RHS, …, RHS )| yi

Definition of MTTs
 An MTT is Deterministic if for every pair of q∈Q, σ∈Σ,

there exists at most one rule of the form<q,σ(…)>(…) → …
 Nondeterministic otherwise
 Total if there‟s at least one rule of the form<q,σ(…)>(…) → … for each of them
 Linear if in every right-hand side, each input
variable xi occurs at most onceTranslation realized by MTTs
 The translation realized by M is

τM = { (s,t) ∈ TΣ×TΔ | <q0,s> ⇒* t }where ⇒ is the rewriting relation
 By interpreting R as the set of rewrite rules
 We consider only the Call-by-Value (Inside-Out)

rewriting order in this workInside-Out (IO) Evaluation
 Example<q0, a(x)> → <q1,x>( <q2,x> )<q1, e>(y) → b(y, y)<q2, e>→ c<q2, e>→ d<q0, a(e)> ⇒ <q1,e>( <q2,e> ) ⇒ <q1,e>( c ) ⇒ b(c,c)⇒ <q1,e>( d ) ⇒ b(d,d)⇒ b( <q2,e>, <q2,e> )Why Nondeterminism and Why IO?
 IO-Nondeterminism in XML translation

languages
 In pattern matching (XDuce) match(e)with pat1 -> e1 | pat2 -> e2

 If e matches both pat1 and pat2, then it nondeterminisiticallychooses e1 or e2

 Approximation of Turing-complete languages(XSLT, …)
 if(complicated-condition) then e1 else e2

 (complicated-condition) may not be able to be modeled byMTTs

Multi-Return Macro Tree Transducer(mr-MTT) An mr-MTT is a tuple M = (Q, Σ, Δ, q0, R) where Q : Doubly ranked set of states (#params, #retvals) Σ : Ranked set of input alphabet
 Δ : Ranked set of output alphabet q0 : Initial state of rank (0, 1)
 R : Set of rules of the following form:<q, σ(x1,…,xk)>(y1, …, ym) → RHS
RHS ::= LET* (TC, …, TC)
LET ::= let (z1,…,zn) = <q,xi>(TC, …, TC) in
TC ::= δ(TC, …, TC) | yi | zi

MTT vs mr-MTT ≒ Tree vs DAG
 MTT

 mr-MTT<q, a(x)>(y) →b(<q,x>(c(y)), <q,x>(d(y)))<q, a(x)>(y) →let (z1,z2) = <q,x>(c(y)) in(d(z1), z2)

db
<q,x>

<q,x>

<q,x>

cdcyyyNotations
 T : the class of translation realized by top-down TTs
 MT : the class of translations realized by MTTs

 MM : the class of translations realized by mr-MTTs
 d-MM (for d ∈ N) : the class of translations realizable bymr-MTTs whose return-tuples are at most length dPrefix D stands for “deterministic”, t for “total”, and L for “linear”. E.g.,
 DMT : the class of translations realized by deterministic MTTs

 LDtT : the class of translations realized by linear deterministic total TTs

Good Properties of mr-MTTs

Expressiveness Question:

Does the „multi-return‟ feature reallyadds any power to MTTs?
 Answer:

Yes, it does! (for nondetermistic MTTs)

Expressiveness of Det. Mr-MTT DMT = DMM(Corollary 5)

 Intuition: State Splitting

a state q returning n-tuple of trees≒
n states q1 … qn where qi returns thei-th component of the return value of q.

Expressiveness of Nondet. 1-MM
 MT ⊊ 1-MM

(Proposition 12)

 Intuition: copying by „let‟ variables adds

some power<q0,b(x1,x2)> →let z = <q,x1>(a,a) in<q,x2>( z, z )<q0,b(x1,x2)> →<q,x2>( <q,x1>(a,a), <q,x1>(a,a) )Expressiveness of 2-MM
 1-MM ⊊ 2-MM

(Theorem 13)

 Witnessed by the „twist‟ translation in the paperrrsa

AaBaAbAe

EeErszrrbAb

BaBbBeEeE

Expressiveness of d-MM
 Conjecture d-MM ⊊ (d+1)-MMfor every d ≧ 1

Closure under composition
 MTTs are very poor in composition:
 LHOM ; MT ⊈ MT
 MT ; DtT ⊈ MT

 For mr-MTTs:
 DT ; MM ⊆ MM

 MM ; DtT ⊆ MM(Theorem 11)

Proof Sketch
 DT ; MM ⊆ MM
 Proof. Product construction

P : the set of states of the DT
Q : the set of states of the lhs MM→ MM with set of states P×Q can simulate thecomposition (rules for the state (p,q) are obtainedby „applying‟ q to rules for p, in which we needvariable-bindings by „let‟).
 MM ; DtT ⊆ MM
 Proof. (A variant of) product construction

Q : states of lhs MM, P : states of DtT→ MM with set of states Q, where ranks of eachq∈Q is multiplied by |P| (a state with m params& d retvals becomes m|P| params & d|P| retvals).

Characterization of mr-MTTs
 Question:

How precisely powerful than MTTs?
 Answer:MM ⊆ LHOM ; MT ; LDtT
 proven through two lemmas
 MM ⊆ 1-MM ; LDtT

 1-MM ⊆ LHOM ; MT

Characterization of mr-MTTs(Simulating multiple return values) MM ⊆ 1-MM ; LDtT

(Lemma 2)

 Intuition: the 1-MM outputs symbolic

representations of tupling and projection
operations, and the LDtT carries them out<q, b(x)> →let (z1,z2) = <q,x> in(a(z1), b(z2))<q, b(x)> →let z = <q,x> inτ(a(1st(z)), b(2nd(z)))

Characterization of mr-MTTs(Simulating „let‟-variable bindings)
 1-MM ⊆ LHOM ; MT(Lemma 3)

 Intuition: MTTs cannot bind and copy treesby ‟let‟-variables, but they can by context
parametersb
Evaluate the 1st„let … in‟bbinbin
LHOM

leaf

leafllll

leaf

leaf

Evaluate the2nd „let … in‟Generate Output
TreeMT

Conclusion
 Multi-Return Macro Tree Transducers= Macro tree transducers with multiple return-values
 Expressiveness DMT = DMM
 MT ⊊ 1-MM ⊊ 2-MM

 Closure under Composition
 DT ; MM ⊆ MM
 MM ; DtT ⊆ MM

 Characterization
 MM = LHOM ; MT ; LDtT