THE COMPLEXITY OF
TRANSLATION MEMBERSHIP FOR
MACRO TREE TRANSDUCERS
Kazuhiro Inaba (The University of Tokyo)
Sebastian Maneth (NICTA & University of New South Wales)
PLAN-X 2009, Savannah

TRANSLATION MEMBERSHIP?
 “Translation Membership Problem” for a tree-to-treetranslation τ :Input: Two trees s and t
 Output: “YES” if τ translates s to t (“NO” otherwise)s？
τt We are especially interested in nondeterministictranslations where τ (s) is a set of trees(i.e., the translation membership problem asks “t ∈τ (s) ?”)APPLICATIONS Dynamic assertion testing / Unit testingassert(run_my_xslt( load_xml(“test-in.xml”) )== load_xml(“test-out.xml”) );How can we check the assertion efficiently?
 How can we check it when the translation depends on externaleffects (randomness, global options, or data form external DB…)?
 “Is there a configuration realizes the input/output pair?” Sub-problem of larger decision problems
Membership test for the domain of the translation[Inaba&Maneth 2008]

KNOWN RESULTS ONCOMPLEXITIES OF TRANSLATION MEMBERSHIP If τ

is a Turing Machine… Undecidable If τ

is a finite composition of
top-down/bottom-up tree transducers… Linear space [Baker 1978]
 Cubic Time [This Work] If τ

is a finite composition ofdeterministic macro tree transducers… Linear time (Easy consequence of [Maneth 2002])

OUTLINE
 Macro Tree Transducers (MTTs)

IO and OI -- Two Evaluation Strategies

 MTTOI Translation Membership is NP-complete… also for finite compositions of MTTIO/MTTOI’s

 MTTIO Translation Membership is in PTIME!!

… also for several extensions of MTTIO!!

 Conclusion and Open Problems

MACRO TREE TRANSDUCER (MTT)
start( A(x1) )→ double( x1, double(x1, E) )double( A(x1), y1) → double( x1, double(x1, y1) )double( B, y1 )→ F( y1, y1 )double( B, y1 )→ G( y1, y1 )
 An MTT M = (Q, q0, Σ , Δ , R) is a set of first-orderfunctions of type Tree(Σ ) * Tree(Δ )k  Tree(Δ ) Each function is inductively defined on the 1st parameter

Dispatch based on the label of the current node Functions are applied only to the direct children of the currentnode Not allowed to inspect other parameter trees(M)TT IN THE XML WORLD
 Simulation of XSLT, XML-QL [Milo&Suciu&Vianu 2000]


Expressive fragment of XSLT and XML-QL can be represented as
a composition of pebble tree transducers (which is a model quite
related to macro tree transducers)

 TL – XML Translation Language [MBPS 2005]


A translation language equipping Monadic Second Order Logic as
its query sub-language, representable by 3 compositions of MTTs.

 Exact Type Checking [MSV00, Tozawa 2001,Maneth&Perst&Seidl 2007, Frisch&Hosoya 2007, …]
 Streaming [Nakano&Mu 2006]
 Equality Test [Maneth&Seidl 2007]
 …

IO AND OI
double( A(x1), y1) → double( x1, double(x2, y1) )double( B, y1 )→ F( y1, y1 )double( B, y1 )→ G( y1, y1 )
 IO (inside-out / call-by-value)：evaluate the arguments first and then call the function
start(A(B))  double( B, double(B, E) ) double( B, F(E, E) )
 F( F(E,E), F(E,E) )or  G( F(E,E), F(E,E) )or double( B, G(E, E) )
 F( G(E, E), G(E, E) )or  G( G(E, E), G(E, E) )

IO AND OI
double( A(x1), y1) → double( x1, double(x2, y1) )double( B, y1 )→ F( y1, y1 )double( B, y1 )→ G( y1, y1 )
 OI (outside-in / call-by-name)： call the function firstand evaluate each argument when it is used
start(A(B))  double( B, double(B, E) )
 F( double(B, E), double(B, E) )
 F( F(E,E), double(B, E) )  F( F(E,E), F(E,E) ) F( F(E,E), G(E,E) ) F( G(E,E), double(B, E) )  F( G(E,E), F(E,E) ) F( G(E,E), G(E,E) ) G( double(B, E), double(B, E) )
 G( F(E,E), double(B, E) )  G( F(E,E), F(E,E) ) G( F(E,E), G(E,E) ) G( G(E,E), double(B, E) )  G( G(E,E), F(E,E) ) G( G(E,E), G(E,E) )IO OR OI?
 Why we consider two strategies?

IO is usually a more precise approximation of originallydeterministic programs:// f(A(x))
f(A(x))
f(A(x))
g(A(x))
h(A(x), y) if ≪complex_choice≫ then e1 else e2
 e1
 e2
 h(x, f(x))
 B(y, y)

OI has better closure properties and a normal form:

For a composition sequence of OI MTTs, there exists a certain
normal form with a good property, while not in IO. (explained later)

RESULTS∧TRANSLATION MEMBERSHIP FOR MTTOIBut, not∨∨ MTTOI Translation Membership is NP-hard

x1 problem
x1 x1 ￢
Proof is by reduction from the 3-SAT￢ ￢There is an MTTOI translation that takes an input encoding
x1 twox1 x1
natural numbers (c and v), and generates all (and only) satisfiable
3-CNF boolean formulas with c clauses and v variables.
∧e.g.,

A2clauses∨
A
B

3variables

∨

x1 x2

τ

x3

B

Z

x2x3

∧

orB

x1

∨

￢ x2x1∨x3

x1x2 ￢x3

TRANSLATION MEMBERSHIP FOR MTTOI ‘Path-linear’ MTTOI Translation Membership is in NP[Inaba&Maneth 2008]
Path-linear ⇔ No nested state calls to the same child nodef( A(x1, x2) )  g(x1, g(x2, B)) // okf( A(x1, x2) )  g(x1, g(x1, B)) // badf( A(x1, x2) )  h(x1, g(x2, B) , g(x2, C)) // okProof is by the “compressed representation”
The set τ (s) can be represented as a single “sharing graph”(generalization of a DAG) of size O(|s|) [Maneth&Bussato 2004] Navigation (up/1st child/next sibling) on the representation can bedone in P only if the MTT τ is a path-linear.
 Corollary: MTTOI Translation Membership is in NP


Proof is by the ‘Garbage-Free’ form in the next page…

K-COMPOSITIONS OF MTTS:

TRANSLATION MEMBERSHIP FOR MTTOIK AND MTTIOK MTTOIk

(k≧1) Translation Membership is NP-complete

Proof is by the Garbage-Free Form [Inaba&Maneth 2008]
Any composition sequence of MTT OI’s
τ = τ 1 ； τ 2 ； … ； τ k can be transformed to a
“Garbage-Free” sequence of path-linear MTTOI’sτ = ρ 1 ； ρ 2 ； … ； ρ 2k where for any (s,t) with t∈τ (s),there exists intermediate treess1∈ρ 1 (s), s2∈ρ 2 (s1), …, t∈ρ 2k (s2k-1) such that |si|≦ c |t| by NP-oracle we can guess all si’s
 MTTIOk(k≧2) Translation Membership is NP-complete

Proof is by Simulation between IO and OI [Engelfriet&Vogler 1985]
MTTOI ⊆ MTTIO ； MTTIO

andMTTIO ⊆ MTTOI ； MTTOIMAIN RESULT:TRANSLATION MEMBERSHIP FOR MTTIO MTTIO Translation Membership is in PTIME(for an mtt with k parameters, O(nk+2))

Proof is based on the Inverse Type Inference[Engelfriet&Vogler 1985, Milo&Suciu&Vianu 2000]
For an MTT τ and a tree t, the inverse image τ -1 (t) is aregular tree languageInstead of “t ∈ τ (s)”, check “s ∈ τ -1(t)”-1(t)
 First, construct the bottom-up tree automaton recognizing τ Then, run the automaton on s.

PITFALL
The automaton may have 2|t|states in the worst case.

PTIME SOLUTION
Do not fully instantiate theautomaton. Run it whileconstructing it on-the-fly.

EXAMPLE (1) τ=st( A(x1) )db( A(x1), y1)
db( B, y1 )db( B, y1 )→ db( x1, db(x2, E) )→ db( x1, db(x2, y1) )→ F( y1, y1 )→ G( y1, y1 )s = A(B),t = F(G(E,E), G(E,E))

 State of the inverse-type automaton :: {st} ∪ ({db}×V(t))

AB 2V(t)whereV(t) isthe
thestate
set ofq allsuch
subtreesof t
We assignthat:A
qA (st) = qB (db, qB(db,E)) = qB (db, {G(E,E)}) = {F(G(E,E), G(E,E))}qA (db, E) = qB (db, qB(db,E))= {F(G(E,E), G(E,E))}qA (db, G(E,E)) = qB (db, qB(db,G(E,E)))= {}qA (db, F(G(E,E), G(E,E))) = …
= {}We assign the state qB such that:qB (st)= {}qB (db, E)= { G(E,E) }// F(E,E) ∉ V(t)qB (db, G(E,E))= { F(G(E,E), G(E,E)) } // G(G,G) ∉ V(t)qB (db, F(G(E,E), G(E,E))) = {}EXAMPLE (2) τ=st( A(x1) )db( A(x1), y1)
db( B, y1 )db( B, y1 )→ db( x1, db(x1, E) )→ db( x1, db(x1, y1) )→ F( y1, y1 )→ G( y1, y1 )s = A(B),t = F(G(E,E), F(E,E))

 State of the inverse-type automaton :: {st} ∪ ({db}×V(t))

A

B

where
setq of(db,E))
all subtreesof{G(E,E),F(E,E)})tqA V(t)(st) =is qthe
(db,=q(db,BBB
qA (db, E)= qB (db, qB(db,E))
qA (db, G(E,E))= qB (db, qB(db,G(E,E)))qA (db, F(E,E))= qB (db, qB(db,F(E,E)))qA (db, F(G(E,E), G(E,E)))=…

 2V(t)
= {}
= {}
= {}
= {}
= {}

qB (st)= {}qB (db, E)= { G(E,E), F(E,E) }qB (db, G(E,E))= {} // F(G,G) and G(G,G) ∉ V(t)qB (db, F(E,E))= {} // F(F,F) and G(F,F) ∉ V(t)qB (db, F(G(E,E), F(E,E))) = {} // …

NOTE
 Complexity:

 At each node of s, one function of type{st}∪({db}×V(t))  2V(t) is computed
 {st}∪({db}×V(t))  2V(t) ≡ 2V(t)×({st}∪({db}×V(t)))
Each function is of size O( |V(t)|2 ), which is computed pereach node (O(|s|) times) (and, computation of each entryof the function requires O(|t|2) time)  O( |s| |t|4 ) time

 MTTOI also has regular inverse image, but the inverse-type automaton may have 2^2^|t| many states in theworst case Computing even a single state requires EXPTIMESEVERAL EXTENSIONSAs long as the inverse type issufficiently small, we can apply thesame technique.

 Variants of MTTs with PTIME Translation Membership



MTTIO with TAC-look-ahead

Rules are chosen not only by the label of the current node, but by
a regular look-ahead and (dis)equality-check on child subtreesf( A(x1,x2) ) s.t. x1≡x2→ C( f(x1) )f( A(x1,x2) ) s.t. x1 has even number of nodes→ D( f(x1), f(x2) )f( A(x1,x2) ) otherwise→ E( f(x1), f(x2) )Multi-Return MTTIOEach function can return multiple tree fragments (tuples of trees)f( A(x1,x2) )  let (z1,z2) = g(x1) in D( z1, C(z2) )g( A(x1,x2) )  ( f(x1), f(x2) )Finite-copying MTTOIOI, but each parameter is copied not so many times.

CONCLUSION AND OPEN PROBLEMS Complexity of Translation Membership isNP-complete for
MTTOIk (k ≧ 1), MTTIOk (k ≧ 2)
 Higher-Order MTT, Macro Forest TT, …


PTIME for

MTTIO (+ look-ahead and multi-return) Open Problems


MTTOI with at most one accumulating parameter

Our encoding of SAT used 3 parameters, which actually can bedone with 2. How about 1?

MTTIO with holes [Maneth&Nakano PLAN-X08]
It is an extension of IO MTTs, but has more complex inverse-type.

THANK YOU!