The Complexityof Tree Transducer
Output Languages
FSTTCS 2008, Bengaluru

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

―Complexity of Output Languages‖
 Given…
 A language

L ⊆ TΣ
(Trees over Σ) A relation (nondeterministic translation)τ ⊆ TΣ×TΔ (from TΣ to TΔ)
 What is the complexity of the language

τ(L) ⊆ TΔ ?

(i.e., for t ∈ TΔ, how is it computationally hardto determine whether t ∈ τ(L) or not?)Classic Results τ:Program of Turing-Machine Undecidable

 L : Regular String Language τ: Nondeterministic Finite State Transduction τ(L) is regular!
  The membership of τ(L) is solved inO(n) time, O(1) space Corollary: for τ∈ Finitely Many Compositions ofNondeterministic FST, τ(L) is regularTrees?
 L : Regular Tree Language τ: Finitely Compositions ofNondet. Finite-State Tree Transducers
 Beyond Regular Tree Language (Intuitively…) Due to Copying τ(t) → x(t, t)

 In DSPACE(n)is an instance of FSTT

[Baker1978]

 i.e., Deterministic Context-Sensitive

Recent Result [Maneth2002, FSTTCS]
 L : Regular Tree Language τ: Finite Compositions of

Total Deterministic Macro Tree Transducers
 == Tree Transducers extended with ―accumulatingparameters‖ for each state In DSPACE(n) Still, Deterministic Context-SensitiveToday‘s Target!
 L : Regular Tree Language τ: Finite Compositions ofNondeterministic Macro Tree Transducer Is it still context-senstive? – Yes. NSPACE(n) What about the time complexity? – NP-complete

Outline What is/Why Macro Tree Transducers?
 Review of the Proof for Deterministic Case ―Garbage-free‖ Lemma ―Translation Membership‖ Problem

 SummaryMacro Tree Transducer (MTT) Q : Finite Set of States q0:

Initial State Σ : Input Alphabet
 Δ : Output Alphabet
 R : Set of Rewrite Rules of form:<q, σ(x1,…,xk)>( y1,…, ym )  r
where r ::= δ(r, …, r) | <q, xi>(r, …, r) | yjExample of an MTT
<q0, a(x)>() <q0, b(x)>() f( <q1, x>( a(e) ), <q2,x>() ) f( <q1, x>( b(e) ), <q2,x>() )<q1, a(x)>(y) <q1, b(x)>(y) <q1, e>(y) <q1, x>( a(y) ) ) <q1, x>( b(y) ) )y<q2, a(x)>() <q2, b(x)>() <q2, e>() a( <q2,x>() ) b( <q2,x>() )
e





<q0, a(b(b(e))>()→ f( <q1,b(b(e))>(a(e)), <q2,a(e)>() )→ f( <q1,b(e)>(a(a(e)), <q2,a(e)>() )→ f( <q1,e>(a(a(a(e))), <q2,a(e)>() ) → …

fabababbabeee(Choice of Semantics)
 Functional Programming + Laziness +Nondeterminism  We take the Runtime-Choice Semantics:
 <coin, a>  0 | 1
 <twocoins, a>(y)  c(y, y) <twocoins, a>( <coin,a>() ) *

{ c(0,0), c(0,1), c(1,0), c(1,1) } Because of its composability:

MTT ; LT ⊆ MTT

MTT*(REGT)= PTT*(REGT)= ATT*(REGT)=…
OI-Hierarchy
DtMTT*(REGT)

Context Free

T*(REGT)IO-Hierarchy
MSOTT*(REGT)
RegularReview:
DSPACE(n) Membership for Det. MTTs
 Given a (fixed) pair of Input regular language L and Composition sequenceτ1 ; … ; τn oftotal deterministic mtts
 and a tree t,t ∈ (τ1 ; … ; τn )(L)in linear space wrt |t|?

 How can we test

Review:
DSPACE(n) Membership for Det. MTTs
Guess the input s ∈ L
 Calculate (τ1 ; … ; τn )(s)Is this a possible
 If (τ1 ; … ; τn )(s) = t, then t is in the output output
language!
from Otherwise, try another input tree sτ1 ; … ; τ n ?


Guess an input:
sComputes Compute:=τ (s)sCompute:=τ (s) sCompute s1

τ1s12

τ2s1

2n-1nτns2

Sn-1= tsn?

Review:
DSPACE(n) Membership for Det. MTTs


In order to carry out the algorithm in DSPACE(|t|) …
 The sizes |s|, |s1|, |s2|, …, |sn| must be linearly bounded by |t|
i.e., there must be a constant c independent from t s.t. |s| ≦ c|t|

 Each step τ of the computation must be done in linear space

The translation musthave‗no garbage‘!

τ1s

τ2s1

τns2

Sn-1= tsn?

Review:DSPACE(n) Membership for Det. MTTs ‗Garbage-Free‘ Lemma
 For any input language L and mttsτ1, …, τn, thereexists L‘ and τ‘1, …, τ‘n such that
(τ1;…;τn)(L) == (τ‘1;…;τ‘n)(L‘)
and every τ‘i is ‗non-deleting‘ ( |in| ≦ 2|out| ) Linear Time (and Space) Computation
 For any total deterministic mtt τand a tree s,τ(s) can be computed in time O( |s| + |τ(s)| )(already known as a folklore result)

NSPACE(n)/NP Output Membership forNondeterministic MTTs
 Guess the input s ∈ L

and all the intermediate trees s1, …, sn-1
 Check whether(s,s1)∈τ1, (s1,s2)∈τ2, …, (sn-1, t) ∈τn If it is, then t is in the output language!
 Otherwise, try another s, s2, …, sn-1

∈s

τns1

∈

τ2

∈

τ1

s2

Sn-1t

Key Lemmas ‗Garbage-Free‘ Lemma—Nondet. Version

 NP/NSPACE(n) ―Translation Membership‖

for a single mtt translation

Key Lemma (1):‗Garbage-Free‘ Lemma—Nondet. Version
 Basic Idea
 ―Factor out‖ the deletion τ1 ; τ2 == τ1 ; (D ;τ‘2)== (τ1 ; D) ; τ‘2== ρ1; τ‘2

Decompose τ2to ‗deleting part‘ Dand ‗nondeleting‘ τ‘2

Associativity

Compose τ1 with DThree Types of Deletion
 ―Erasure‖ <q,σ>(y1, y2)  y1

Lemma:
If no erasing, input-deleting, orskipping rule is used during thecomputation, then |in| ≦ 2|out| No new output node is generated at this σ node. Only

returning its parameter.
 ―Input-Deletion‖ <q, σ(x1, x2)>()  δ( <q, x1>() ) Discarding the ―x2‖ subtree!

 ―Skipping‖ <q, σ(x1)>()  <q, x1>()

 Occurs only at monadic node. No new output isgenerated here. Just going down to its child node.

Eliminating
The Three Types of Deletion
 Achieved by heavily manipulating the rules
 For details, please consult the paper One of the difficulties compared to thedeterministic case: Inline-Expansiony <q, b(x1,x2)>  c( <p,x1>(<q,x2>(e)) ) <q, a>(y)(Assume we know that ‗b‘‘s child is always ‗a‘) <q, b(x1,x2)>  c( <p,x1>( e ) )With Nondeterminism,
Inline-Expansion is Not Easye
 <q, a>()f
 <q, b(x)>()  <p,x>( <q,x>() ) <p, a>(y)  c(y, y) <q, a>()<q, b(a)>()→ <p,a>( <q,a>() )→ c( <q,a>(), <q,a>() )→ c( e, f )e <q, a>()f
 <q, b(x)>()  <p,x>( e ) <q, b(x)>()  <p,x>( f ) <p, a>(y) c(y, y) <q, a>()Different
Translation!
<q, b(a)>()→ <p,a>(e) → c( e, e )or→ <p,a>(f) → c( f, f )Solution:―MTT with Choice and Failure‖ We have extended MTTs with ―inline‖

nondeterminism Allows inline-expansion for free!

 Actually, we prove the output language

complexity for mtt-cfs
e <q, a>()f
 <q, b(x)>()  <p,x>( +(e, f) )
 <p, a>(y) c(y, y) <q, a>()<q, b(a)>()→ <p,a>( +(e,f) )→ c( +(e,f), +(e,f) )→ c( e, f )Key Lemma (2):―Translation Membership‖ of single τi Given a pair (si-1, si) of trees,

we can determine whether (si-1, si) ∈ τi
in linear-space & polynomial time wrt |si-1 |+|si|in nondet. Turing machine Naively Applying the folklore deterministic

computation takes O(|si-1 |+ |τ(si-1)|) time/space New Idea is Necessary

―Translation Membership‖ of single τi
OK. Similar
Bad.
Nondet. Time decomposition
 Naively Applying theLinear
Computation
Linear MTTs mayworks also forfor Deterministic MTTs:
read each nodeNondet. MTTs
Need Moremultiple times
 Fails.
Sophisticated ItCompression!
relied on the decompostion of an MTT into Linear

MTTs (each input variable xi occurs at most once ineach rule), …and the fact that deterministic linear MTTs readeach input node at most once, …which allows to compress the output tree as a DAG
for both saving space and sharing computations

Example: Linear Nondet. MTT
Reading Some Node Twice <q, b(x1,x2)>()
 <q, a>()
 <q, a>() <p, a>(y) <p,x1>( <q,x2>() )ef g(y, y)Solution: Compression
by Context-Free Tree Grammar
 The set all outputs τi(si-1)of an MTT canbe represented by a CFTG of size
proportional to |si-1| [MB04]
τi

∈

Si-1

τi(si-1)
siNavigation (up,1stchild, nextsibl) on the compressed
representation is efficient for linear mtts

Summary
 Composition sequence τ1 ; …; τn of mtts can beconverted to an equivalent ‗garbage-free‘composition
 Translation Membership of any mtt is inNP/NSPACE(n)  Altogether, the output language complexity ofmtt-compositions is NP/NSPACE(n) Corollary: OI-hierarchy, PTT*(REGT), ATT*(REGT),… is in NP/NSPACE(n) Current Status (Unpublished): NSPACE(n)DSPACE(n)