Top-Down Tree Transducers .28TOP.29 Tree transducer

1 top-down tree transducers (top)

1.1 examples of rules , intuitions on semantics
1.2 semantics term rewriting
1.3 determinism , domain
1.4 properties of dtop

top-down tree transducers (top)

a top t tuple (q, Σ, Γ, i, δ) such that:

q finite set, set of states;
Σ finite ranked alphabet, called input alphabet;
Γ finite ranked alphabet, called output alphabet;
i subset of q, set of initial states; and




δ


{\displaystyle \delta }

set of rules of form



q
(
f
(

x

1


,
…
,

x

n


)
)
→
u


{\displaystyle q(f(x_{1},\dots ,x_{n}))\to u}

, f symbol of Σ, n arity of f, q state, , u tree on Γ ,



q
×
1..
n


{\displaystyle q\times 1..n}

, such pairs being nullary.

examples of rules , intuitions on semantics

for instance,

q
(
f
(

x

1


,
…
,

x

3


)
)
→
g
(
a
,

q
′

(

x

1


)
,
h
(

q
″

(

x

3


)
)
)


{\displaystyle q(f(x_{1},\dots ,x_{3}))\to g(a,q (x_{1}),h(q (x_{3})))}

is rule – 1 customarily writes



q
(

x

i


)


{\displaystyle q(x_{i})}

instead of pair



(
q
,

x

i


)


{\displaystyle (q,x_{i})}

– , intuitive semantics that, under action of q, tree f @ root , 3 children transformed into

g
(
a
,

q
′

(

x

1


)
,
h
(

q
″

(

x

3


)
)
)


{\displaystyle g(a,q (x_{1}),h(q (x_{3})))}

where, recursively,




q
′

(

x

1


)


{\displaystyle q (x_{1})}

,




q
″

(

x

3


)


{\displaystyle q (x_{3})}

replaced, respectively, application of




q
′



{\displaystyle q }

on first child , application of




q
″



{\displaystyle q }

on third.

semantics term rewriting

the semantics of each state of transducer t, , of t itself, binary relation between input trees (on Σ) , output trees (on Γ).

a way of defining semantics formally see



δ


{\displaystyle \delta }

term rewriting system, provided in right-hand sides calls written in form



q
(

x

i


)


{\displaystyle q(x_{i})}

, states q unary symbols. semantics



[

[
q
]

]


{\displaystyle [\![q]\!]}

of state q given by

[

[
q
]

]
=
{
u
↦
v
∣
u

 is tree on 

Σ
,
 
v

 is tree on 

Γ

, and 

q
(
u
)

→

δ


∗


v
}
.


{\displaystyle [\![q]\!]=\{u\mapsto v\mid u{\text{ tree on }}\sigma ,\ v{\text{ tree on }}\gamma {\text{, , }}q(u)\to _{\delta }^{*}v\}.}

the semantics of t defined union of semantics of initial states:

[

[
t
]

]
=

⋃

q
∈
i


[

[
q
]

]
.


{\displaystyle [\![t]\!]=\bigcup _{q\in i}[\![q]\!].}



determinism , domain

as tree automata, top said deterministic (abbreviated dtop) if no 2 rules of δ share same left-hand side, , there @ 1 initial state. in case, semantics of dtop partial function input trees (on Σ) output trees (on Γ), semantics of each of dtop s states.

the domain of transducer domain of semantics. likewise, image of transducer image of semantics.

properties of dtop

dtop not closed under union: case deterministic word transducers.
the domain of dtop regular tree language. furthermore, domain recognisable deterministic top-down tree automaton (dtta) of size @ exponential in of initial dtop.




that domain dtta-recognizable not surprising, considering left-hand sides of dtop rules same dtta. reason exponential explosion in worst case (that not exist in word case), consider rule



q
(
f
(

x

1


,

x

2


)
)
→
g
(

p

1


(

x

1


)
,

p

2


(

x

1


)
,

p

3


(

x

2


)
)


{\displaystyle q(f(x_{1},x_{2}))\to g(p_{1}(x_{1}),p_{2}(x_{1}),p_{3}(x_{2}))}

. in order computation succeed, must succeed both children. means right child must in domain of




p

3




{\displaystyle p_{3}}

. left child, must in domain of both




p

1




{\displaystyle p_{1}}

,




p

2




{\displaystyle p_{2}}

. generally, since subtrees can copied, single subtree can evaluated multiple states during run, despite determinism, , unlike dtta. construction of dtta recognising domain of dtop must account sets of states , compute intersections of domains, hence exponential. in special case of linear dtop, dtop each




x

i




{\displaystyle x_{i}}

appears @ once in right-hand side of each rule, construction linear in time , space.




the image of dtop not regular tree language.




consider transducer coding transformation



f
(
x
)
→
g
(
x
,
x
)


{\displaystyle f(x)\to g(x,x)}

; is, duplicate child of input. done rule



q
(
f
(

x

1


)
)
→
g
(
p
(

x

1


)
,
p
(

x

1


)
)


{\displaystyle q(f(x_{1}))\to g(p(x_{1}),p(x_{1}))}

, p encodes identity. then, absent restrictions on first child of input, image classical non-regular tree language.




however, domain of dtop cannot restricted regular tree language. say, given dtop t , language l, 1 cannot in general build dtop




t
′



{\displaystyle t }

such semantics of




t
′



{\displaystyle t }

of t, restricted l.




this property linked reason deterministic top-down tree automata less expressive bottom-up automata: once go down given path, information other paths inaccessible. consider transducer coding transformation



f
(
x
,
y
)
→
y


{\displaystyle f(x,y)\to y}

; is, output right child of input. done rule



q
(
f
(

x

1


,

x

2


)
)
→
p
(

x

2


)


{\displaystyle q(f(x_{1},x_{2}))\to p(x_{2})}

, p encodes identity. let s want restrict transducer finite (and thus, in particular, regular) domain



{
f
(
c
,
a
)
,
 
f
(
c
,
b
)
}


{\displaystyle \{f(c,a),\ f(c,b)\}}

. must use rules



q
(
f
(

x

1


,

x

2


)
)
→
p
(

x

2


)
,
 
p
(
a
)
→
a
,
 
p
(
b
)
→
b


{\displaystyle q(f(x_{1},x_{2}))\to p(x_{2}),\ p(a)\to a,\ p(b)\to b}

. in first rule,




x

1




{\displaystyle x_{1}}

not appear @ all, since nothing produced left child. thus, not possible test left child c. in contrast, since produce right child, can test or b. in general, criterion dtop cannot test properties of subtrees not produce output.




dtop not closed under composition. problem can solved addition of lookahead: tree automaton coupled transducer, can perform tests on domain transducer incapable of.




this follows point domain restriction: composing dtop encoding identity on



{
f
(
c
,
a
)
,
 
f
(
c
,
b
)
}


{\displaystyle \{f(c,a),\ f(c,b)\}}

1 encoding



f
(
x
,
y
)
→
y


{\displaystyle f(x,y)\to y}

must yield transducer semantics



{
f
(
c
,
a
)
↦
a
,
 
f
(
c
,
b
)
↦
b
}


{\displaystyle \{f(c,a)\mapsto a,\ f(c,b)\mapsto b\}}

, know not expressible dtop.




the typechecking problem—testing whether image of regular tree language included in regular tree language—is decidable.
the equivalence problem—testing whether 2 dtop define same functions—is decidable.




^ baker, b.s.: composition of top-down , bottom-up tree transductions. inf. control 41(2), 186–213 (1979)
^ maneth, sebastian (december 2015). survey on decidable equivalence problems tree transducers . international journal of foundations of computer science. 26 (08): 1069–1100. doi:10.1142/s0129054115400134. 
^ decidability results concerning tree transducers . www.inf.u-szeged.hu.