11institutetext: Universität Bremen, Germany
11email<EMAIL_ADDRESS>
# Attributed Tree Transducers for Partial Functions

Sebastian Maneth  Martin Vu

###### Abstract

Attributed tree transducers (atts) have been equipped with regular look-around
(i.e., a preprocessing via an attributed relabeling) in order to obtain a more
robust class of translations. Here we give further evidence of this
robustness: we show that if the class of translations realized by
nondeterministic atts with regular look-around is restricted to partial
functions, then we obtain exactly the class of translations realized by
deterministic atts with regular look-around.

##  1 Introduction

Attributed tree transducers (atts) [10] are a well known formalism for
defining tree translations. They are attractive, because they are strictly
more expressive than top-down tree transducers and they closely model the
behavior of attribute grammars [15, 16]. Since attribute grammars are
deterministic devices, atts also have typically been studied in their
deterministic version.

But atts also have some deficiencies. For instance, they do not generalize the
(deterministic) bottom-up tree translations [12]. One possibility to remedy
this deficiency is to equip atts with _regular look-around_ [2]. The resulting
class of translations is more robust in the sense that (_i_) it does
generalized deterministic bottom-up tree translations [5], (_ii_) it is
equivalent to tree-to-dag-to-tree translations that are definable in MSO logic
[2], and (_iii_) it is characterized by natural restrictions of macro tree
transducers [14].

In this paper we present another advantage of adding regular look-around: we
show that every nondeterministic att (with or without regular look-around)
that is _functional_ can be realized by a _deterministic_ att with regular
look-around (and such a transducer can be constructed). In general it is a
desirable and convenient property of a nondeterministic translation device
that its restriction to functional translations coincides precisely with the
translations realized by the corresponding deterministic version of that
device. Let us consider some classical examples of translation devices for
which this property holds:

  * •

two-way strings transducers (“2GSM”) [7, Theorem 22][19, Theorem 3],

  * •

top-down tree transducers with look-ahead [6, Theorem 1], and

  * •

macro tree transducers [8, Corollary 36].

In contrast, these are examples for which the property does _not_ hold:

  * •

one-way string transducers (“GSM”),

  * •

top-down and bottom-up tree transducers, and

  * •

attributed tree transducers.

To see that functional top-down tree transducers and functional GSMs are
strictly more expressive than their deterministic counterparts, consider the
following translation: Let monadic input trees of the form $a^{n}(e)$ be
translated to $a^{n}(e)$ while input trees of the form $a^{n}(f)$ are
translated to the single leaf $f$. A deterministic top-down tree transducer
(or a deterministic GSM) cannot realize this translation, because it has to
decide whether or not to output $a$-nodes, before it sees the label of the
input leaf (viz. the right end of the string).

Given a relation $R$, a _uniformizer of $R$_ is a function $f_{R}\subseteq R$
such that $f_{R}$ and $R$ have the same domain. Engelfriet [6] showed that for
any nondeterministic top-down tree translation $R$, a uniformizer of $R$ can
be constructed as a deterministic top-down tree transducer with look-ahead
($dt^{R}$) . Since the latter type of transducer is closed under composition
[5], it follows that for any composition of top-down (and bottom-up) tree
transductions that is functional, an equivalent $dt^{R}$ can be constructed.
Whenever several rules of the given transducer are applicable, the uniformizer
chooses the first one of them (in some order); the regular look-ahead is used
to determine which rules are applicable. For an overview over different
uniformization results in automata theory see [4].

Now consider a functional attributed tree transducer (att). Its input trees
are over the binary labels $f$ and $g$ and the leaf label $e$ and its output
trees are over the unary label $d$ and the leaf label $e$. The att outputs
$d^{n}(e)$ if there exists a first $g$-node in reverse pre-order and $n$ is
the size of the subree rooted at that node (no output is produced, if no such
$g$-node exists). This translation cannot be realized by any deterministic
att, even if it uses regular look-ahead. However, there is a deterministic att
with _regular look-around_ that realizes the translation.

Subsequently, we show that any (possibly circular) nondeterministic att $A$
effectively has a uniformizer that is realized by a deterministic att with
look-around. To construct such a deterministic att $D$ with regular look-
around, we first construct a nondeterministic (and in general non-functional)
top-down relabeling $T$ and a deterministic att $D^{\prime}$ which operate as
follows: Informally, the top-down relabeling $T$ specifies which rules the
deterministic att $D^{\prime}$ should apply. More precisely, given an input
tree $s$, $T$ annotates all nodes of $s$ by rules of $A$. At every node, the
deterministic att $D^{\prime}$ applies exactly those rules with which the
nodes are annotated. In particular, $T$ annotates the nodes of $s$ such that
$D^{\prime}$ simulates a _uniform_ translation of $A$, that is, a translation
in which if multiple instance of an attribute $\alpha$ access the same node
$v$, then all these instances of $\alpha$ need to apply the same rule. With
the result of [6], a look-around $U$ can be constructed that realizes a
uniformizer of the translation of $T$. With the deterministic att
$D^{\prime}$, this look-around $U$ yields $D$.

The existence of a uniformizer realized by a deterministic att with regular
look-around for any att implies that a composition of $n$ atts (with or
without look-around) that is functional can be simulated by a composition of
$n$ deterministic atts with look-around. This also implies that for any
functional att there is effectively an equivalent deterministic att with look-
around.

An abridged version of this paper has been accepted for publication at the
Conference on Implementation and Application of Automata (CIAA 2024).

##  2 Preliminaries

Denote by $\mathbb{N}$ the set of natural numbers. For $k\in\mathbb{N}$, we
denote by $[k]$ the set $\\{1,\dots,k\\}$.

A set $\Sigma$ is _ranked_ if each symbol of $\Sigma$ is associated with a
_rank_ , that is, a non-negative integer. We write $\sigma^{k}$ to denote that
the symbol $\sigma$ has rank $k$. By $\Sigma_{k}$ we denote the set of all
symbols of $\Sigma$ which have rank $k$. For $k^{\prime}\neq k$, we define
that $\Sigma_{k^{\prime}}$ and $\Sigma_{k}$ are disjoint. If the set $\Sigma$
is finite then we call $\Sigma$ a _ranked alphabet_.

The set $T_{\Sigma}$ of trees over $\Sigma$ is defined as the smallest set of
strings such that if $\sigma\in\Sigma_{k}$, $k\geq 0$, and
$t_{1},\dots,t_{k}\in T_{\Sigma}$ then $\sigma(t_{1},\dots,t_{k})$ is in
$T_{\Sigma}$. For $k=0$, we simply write $\sigma$ instead of $\sigma()$.

The nodes of a tree $t\in T_{\Sigma}$ are referred to by strings over
$\mathbb{N}$. In particular, for $t=\sigma(t_{1},\dots,t_{k})$, we define
$V(t)$, the set of nodes of $t$, as $V(t)=\\{\epsilon\\}\cup\\{iu\mid
i\in[k]\text{ and }u\in V(t_{i})\\}$, where $\epsilon$ is the _empty string_.
For better readability, we add dots between numbers, e.g. for the tree
$t=f(a,f(a,b))$ we have $V(t)=\\{\epsilon,1,2,2.1,2.2\\}$. Let
$v,v^{\prime}\in V(t)$. Then we call $v$ a (proper) ancestor of a node
$v^{\prime}$ if $v$ is a (proper) prefix of $v^{\prime}$.

For a node $v\in V(t)$, $t[v]$ denotes the label of $v$, $t/v$ is the subtree
of $t$ rooted at $v$, and $t[v\leftarrow t^{\prime}]$ is obtained from $t$ by
replacing $t/v$ by $t^{\prime}$. For instance, for $t=f(a,f(a,b))$, we have
$t[1]=a$, $t/2=f(a,b)$ and $t[1\leftarrow b]=f(b,f(a,b))$. The _size_ of a
tree $t$ is given by $\text{size}(t)=|V(t)|$.

For a set $\Lambda$ disjoint with $\Sigma$, we define $T_{\Sigma}[\Lambda]$ as
$T_{\Sigma^{\prime}}$ where $\Sigma^{\prime}_{0}=\Sigma_{0}\cup\Lambda$ and
$\Sigma_{k}^{\prime}=\Sigma_{k}$ for $k>0$.

Let $R\subseteq A\times B$ be a relation. We call $R$ a _function_ if
$(a,b),(a,b^{\prime})\in R$ implies $b=b^{\prime}$. We define the _domain of
$R$_ by $\text{dom}(R)=\\{a\in A\mid\exists b\in B:\ (a,b)\in R\\}$.
Analogously, the _range of $R$_ is $\text{range}(R)=\\{b\in B\mid\exists a\in
A:\ (a,b)\in R\\}$. A function $F\subseteq R$ is called a _uniformizer_ of $R$
if $\text{dom}(F)=\text{dom}(R)$. Let $R^{\prime}\subseteq B\times C$. The
composition of $R$ and $R^{\prime}$ is $R\circ R^{\prime}=\\{(a,c)\mid(a,b)\in
R,(b,c)\in R^{\prime}\\}$.

##  3 Attributed Tree Transducers

In the following, we define attributed tree transducers. For an in-depth
introduction to attributed tree transducers, we refer to [13].

A _(partial nondeterministic) attributed tree transducer_ (or $att$ for short)
is a tuple $A=(S,I,\Sigma,\Delta,a_{0},R)$, where

  * •

$S$ and $I$ are disjoint finite sets of _synthesized attributes_ and
_inherited attributes_ , respectively,

  * •

$\Sigma$ and $\Delta$ are ranked alphabets of _input_ and _output symbols_ ,
respectively,

  * •

$a_{0}\in S$ is the _initial attribute_ and

  * •

$R=(R_{\sigma}\mid\sigma\in\Sigma\cup\\{\\#\\})$ is a collection of finite
sets of rules.

We implicitly assume $atts$ to include a unique symbol $\\#\notin\Sigma$ of
rank $1$, the so-called _root marker_ , that only occurs at the root of trees.

In the following, we define the rules of an $att$. Let $\sigma\in\Sigma$ be of
rank $k\geq 0$. Furthermore, let $\pi$ be a variable for nodes. Then the set
$R_{\sigma}$ contains

  * •

arbitrarily many rules of the form $a(\pi)\rightarrow\xi$ for every $a\in S$
and

  * •

arbitrarily many rules of the form $b(\pi i)\rightarrow\xi^{\prime}$ for every
$b\in I$ and $i\in[k]$,

where $\xi,\xi^{\prime}\in T_{\Delta}[\\{a^{\prime}(\pi i)\mid a^{\prime}\in
S,i\in[k]\\}\cup\\{b^{\prime}(\pi)\mid b^{\prime}\in I\\}]$. We define the set
$R_{\\#}$ analogously with the restriction that $R_{\\#}$ contains _no_ rules
with synthesized attributes on the left-hand side and inherited attributes on
the right-hand side. Replacing ‘arbitrarily many rules’ by ‘at most one rule’
in the definition of the rule sets of $R$, we obtain the notion of a
_(partial) deterministic $att$_ (or $datt$ for short). For the $att$ $A$ and
the attribute $a\in S$, we denote by $\text{RHS}_{A}(\sigma,a(\pi))$ the set
of all right-hand sides of rules in $R_{\sigma}$ that are of the form
$a(\pi)\rightarrow\xi$. For $b\in I$, the sets $\text{RHS}_{A}(\sigma,b(\pi
i))$ with $i\in[k]$ and $\text{RHS}_{A}(\\#,b(\pi 1))$ are defined
analogously.

Attributed Tree Translation. We now define the semantics of $A$. Denote by
$T_{\Sigma^{\\#}}$ the set $\\{\\#(s)\mid s\in T_{\Sigma}\\}$. For a given
tree $s\in T_{\Sigma^{\\#}}$, we define

$\text{SI}(s)=\\{\alpha(v)\mid\alpha\in S\cup I,v\in V(s)\\}.$

Furthermore, we define that for the node variable $\pi$, $\pi 0=\pi$ and that
for a node $v$, $v.0=v$. Let $t,t^{\prime}\in T_{\Delta}[\text{SI}(s)]$. We
write $t\Rightarrow_{A,s}t^{\prime}$ if $t^{\prime}$ is obtained from $t$ by
substituting a leaf of $t$ labeled by $\gamma(v.i)$ with $i=0$ if $\gamma\in
S$ and $i>0$ if $\gamma\in I$ by $\xi[\pi\leftarrow v]$, where
$\xi\in\text{RHS}_{A}(s[v],\gamma(\pi i))$ and $[\pi\leftarrow v]$ denotes the
substitution that replaces all occurrences of $\pi$ by the node $v$. For
instance, for $\xi_{1}=f(b(\pi))$ and $\xi_{2}=f(a(\pi 2))$ where $f$ is a
symbol of rank $1$, $a\in S$ and $b\in I$, we have $\xi_{1}[\pi\leftarrow
v]=f(b(v))$ and $\xi_{2}[\pi\leftarrow v]=f(a(v.2))$. Denote by
$\Rightarrow_{A,s}^{+}$ and $\Rightarrow_{A,s}^{*}$ the transitive closure and
the reflexive-transitive closure of $\Rightarrow_{A,s}$, respectively.

The _translation realized by $A$_, denoted by $\tau_{A}$, is the relation

$\\{(s,t)\in T_{\Sigma}\times T_{\Delta}\mid
a_{0}(1)\Rightarrow_{A,s^{\\#}}^{*}t\\},$

where subsequently $s^{\\#}$ denotes the tree $\\#(s)$. If $\tau_{A}$ is a
partial function then we say that $A$ is a _functional_ $att$. We define
$\text{dom}(A)=\text{dom}(\tau_{A})$ and
$\text{range}(A)=\text{range}(\tau_{A})$.

The reader may wonder why the definition of $A$ and its translations involves
the root marker. Informally, the root marker is a technical requirement
without which many translations are not possible. To see which role the root
marker plays in a translation, consider the following translation which cannot
be realized without the root marker.

###### Example 1

Consider the $att$ $A=(S,I,\Sigma,\Delta,a,R)$ where
$\Sigma=\\{f^{2},e^{0}\\}$ and $\Delta=\\{d^{1},e^{0}\\}$. We define
$S=\\{a\\}$ and $I=\\{b\\}$. For the symbol $f$, we define

$R_{f}=\\{\underbrace{a(\pi)\rightarrow d(a(\pi 2))}_{\rho_{1}},\
\underbrace{b(\pi 2)\rightarrow a(\pi 1)}_{\rho_{2}},\ \underbrace{b(\pi
1)\rightarrow b(\pi)}_{\rho_{3}}\ \\}.$

Finally, the rule set for the symbol $e$ and the root marker are given by

$R_{e}=\\{\underbrace{a(\pi)\rightarrow
d(b(\pi))}_{\rho_{4}}\\}\quad\quad\text{and}\quad\quad
R_{\\#}=\\{\underbrace{b(\pi 1)\rightarrow e}_{\rho_{5}}\\},$

respectively. The tree transformation realized by $A$ is defined as follows:
On input $s\in T_{\Sigma}$, where $s$ is of size $n$, $A$ outputs the tree
$d^{n}(e)$. We denote by $d^{n}(e)$ the tree over $\Delta$ with exactly $n$
occurrences of $d$, e.g., $d^{4}(e)$ denotes the tree $d(d(d(d(e))))$. For
instance, for $s=f(e,e)$, the $att$ $A$ outputs the tree $d^{3}(e)$. The
corresponding translation is shown in Figure 1.

$\\#$$f$$e$$e$$a$$b$$e$$d$$d$$d$

$a(1)$$\Rightarrow$$\rho_{1}$$d(a(1.2))$$\Rightarrow$$\rho_{4}$$d^{2}(b(1.2))$$\Rightarrow$$\rho_{2}$$d^{2}(a(1.1))$$\Rightarrow$$\rho_{4}$$d^{3}(b(1.1))$$\Rightarrow$$\rho_{3}$$d^{3}(b(1))$$\Rightarrow$$\rho_{5}$$d^{3}(e)$

Figure 1: The translation from $f(e,e)$ to $d^{3}(e)$ defined by $A$ is
pictured on the left. The corresponding transitions are displayed on the
right. Each $\Rightarrow$ is annotated with the rule used in the corresponding
transition step.

Note that by definition $atts$ are allowed to be _circular_. We say that an
$att$ $A$ is _circular_ if $s\in T_{\Sigma}$, $\alpha(v)\in\text{SI}(s^{\\#})$
and $t\in T_{\Delta}[\text{SI}(s^{\\#})]$ exists such that
$\alpha(v)\Rightarrow_{A,s^{\\#}}^{+}t$ and $\alpha(v)$ occurs in $t$.

Look-Ahead. To define _attributed tree transducer with look-ahead_ , we first
define _bottom-up relabelings_. A _bottom-up relabeling_ $B$ is a tuple
$(P,\Sigma,\Sigma^{\prime},F,R)$ where $P$ is the set of states, $\Sigma$ and
$\Sigma^{\prime}$ are finite ranked alphabets and $F\subseteq P$ is the set of
final states. For $\sigma\in\Sigma$ and $p_{1},\dots,p_{k}\in P$, the set $R$
contains at most one rule of the form

$\sigma(p_{1}(x_{1}),\dots,p_{k}(x_{k}))\rightarrow
p(\sigma^{\prime}(x_{1},\dots,x_{k}))$

where $p\in P$ and $\sigma^{\prime}\in\Sigma^{\prime}$. The rules of $B$
induce a derivation relation $\Rightarrow_{B}^{*}$ defined inductively as
follows:

  * •

Let $\sigma\in\Sigma_{0}$ and $\sigma\rightarrow p(\sigma^{\prime})$ be a rule
in $R$. Then $\sigma\Rightarrow_{B}^{*}p(\sigma^{\prime})$.

  * •

Let $s=\sigma(s_{1},\dots,s_{k})$ with $\sigma\in\Sigma_{k}$, $k>0$, and
$s_{1},\dots,s_{k}\in T_{\Sigma}$. For $i\in[k]$, let
$s_{i}\Rightarrow_{B}^{*}p_{i}(s_{i}^{\prime})$. Furthermore, let
$\sigma(p_{1}(x_{1}),\dots,p_{k}(x_{k}))\rightarrow
p(\sigma^{\prime}(x_{1},\dots,x_{k}))$ be a rule in $R$. Then
$s\Rightarrow_{B}^{*}p(\sigma^{\prime}(s_{1}^{\prime},\dots,s_{k}^{\prime}))$.

For $s\in T_{\Sigma}$ and $p\in P$, we write $s\in\text{dom}_{B}(p)$ if
$s\Rightarrow_{B}^{*}p(s^{\prime})$ for some $s^{\prime}\in
T_{\Sigma^{\prime}}$. The translation realized by $B$ is

$\tau_{B}=\\{(s,s^{\prime})\in T_{\Sigma}\times T_{\Sigma^{\prime}}\mid
s\Rightarrow_{B}^{*}p(s^{\prime})\text{ with }p\in F\\}.$

We define an _attributed tree transducer with look-ahead (or $att^{R}$)_ as a
pair $\hat{A}=(B,A^{\prime})$ where $B$ is a bottom-up relabeling and
$A^{\prime}$ is an $att$. Recall that translations are relations. The
translation realized by $\hat{A}$ is the composition of the translations
realized by $B$ and $A^{\prime}$, that is,

$\tau_{\hat{A}}=\\{(s,t)\in T_{\Sigma}\times
T_{\Delta}\mid(s,s^{\prime})\in\tau_{B}(s)\text{ and
}(s^{\prime},t)\in\tau_{A^{\prime}}\\}.$

Informally, $B$ preprocesses input trees for $A^{\prime}$ with each node $v$,
that is relabeled by $B$, providing $A^{\prime}$ information about the subtree
rooted $v$. We say that $\hat{A}$ is a deterministic $att^{R}$ ($datt^{R}$) if
$A$ is a $datt$. The domain and the range of $\hat{A}$ are defined in the
obvious way.

Look-Around.  _Look-around_ is in concept similar to look-ahead; it is also a
relabeling device that provides additional information to an $att$. However,
it is far more expressive than a look-ahead111The concept of look-around is
introduced in [2] where it is called look-ahead..

To define look-around, we first define _top-down relabelings_. A top-down
relabeling is a deterministic $att$ without inherited attributes
$T=(S,\emptyset,\Sigma,\Sigma^{\prime},a_{0},R)$ where for all
$\sigma\in\Sigma_{k}$, $k\geq 0$, the set $R_{\sigma}$ only contains rules of
the form $q(\pi)\rightarrow\sigma^{\prime}(q_{1}(\pi 1),\dots,q_{k}(\pi k))$
with $\sigma^{\prime}\in\Sigma^{\prime}_{k}$. Note that for a top-down
relabeling, we will henceforth write
$q(\sigma(x_{1},\dots,x_{k}))\rightarrow\sigma^{\prime}(q_{1}(x_{1}),\dots,q_{k}(x_{k}))$
instead $q(\pi)\rightarrow\sigma^{\prime}(q_{1}(\pi 1),\dots,q_{k}(\pi k))\in
R_{\sigma}$. We will also call the attributes of a top-down relabeling states.
Since a top-down relabeling is an $att$, a _top-down relabeling with look-
ahead_ is defined in the obvious way.

An _attributed tree transducer with look-around_ (or $att^{U}$) is a tuple
$\breve{A}=(U,A^{\prime})$ where $A^{\prime}$ is an $att$ and $U$ is a top-
down relabeling with look-ahead. The translation realized by $\breve{A}$ as
well as the domain and the range of $\breve{A}$ are defined analogously as for
$att^{R}$. This means that an $att^{U}$ relabels its input tree in two phases:
First the input tree is relabeled in a bottom-up phase. Then the resulting
tree is relabeled again in a top-down phase before it is processed by
$A^{\prime}$. We say that $\breve{A}$ is a deterministic $att^{U}$
($datt^{U}$) if $A$ is a $datt$. The following results hold.

###### Proposition 1

[18, Lemma 27] Let $A$ be an $att$. Then an equivalent $att$
$A^{\prime}=(S,I,\Sigma,\Delta,a_{0},R)$ can be constructed such that
$R_{\\#}$ contains no distinct rules with the same left-hand side.

###### Proposition 2

[8, Corollary 14] The domain of an $att^{U}$ is effectively regular.

##  4 Functional Compositions of $\mathbf{Atts^{U}}$ are Determinizable

In the remainder of this paper, we prove the following statement: For any
composition of $n$ $atts^{U}$ that is functional an equivalent composition of
$n$ $datts^{U}$ can be constructed. The overall idea is similar to the one in
[6] for top-down tree transducers. More precisely, let $C$ be the composition
of the $atts^{U}$ $A_{1},\dots,A_{n}$. Subsequently, we show that (a) for
$i\in[n]$, a $datt^{U}$ $D_{i}$ can be constructed such that $D_{i}$ realizes
a uniformizer of $A_{i}$ and (b) the composition of $D_{1},\dots,D_{n}$ is
equivalent to $C$. Obviously our statement implies that for any functional
$att^{U}$ there is an equivalent $datt^{U}$.

Before we prove our statement, we remark that in the absence of look-around
our statement does not hold, i.e., a functional composition of $n$ $atts$
without look-around cannot necessarily be simulated by a composition of $n$
$datts$ without-look-around. In particular, we show that there are functional
$atts$ which cannot be simulated by $datts$ without look-around.

###  4.1 On the Necessity of Look-Around

Subsequently, we show that there are tree translations realizable by
functional $atts$ that cannot be realized by any $datt$ even if the $datt$
uses look-ahead. Consider the following example.

###### Example 2

Let $\Sigma=\\{f^{2},g^{2},e^{0}\\}$ and let $\Delta=\\{d^{1},e^{0}\\}$.
Consider the following tree translation. Let $s\in T_{\Sigma}$ and let $v$ be
the first node in reverse pre-order that is labeled by $g$ in $s$. Note that
this means that no proper ancestor of $v$ is labeled by $g$ in $s$. If such a
node $v$ does not exist, i.e., if no input node is labeled by $g$, then no
output is produced. Otherwise, we translate $s$ into $d^{m}(e)$, where $m$
denotes the _size_ of $s/v$. Recall that the size of$s/v$ is the number of its
nodes and that $d^{m}(e)$ denotes the tree over $\Delta$ with exactly $m$
occurrences of $d$, e.g., $d^{3}(e)$ denotes the tree $d(d(d(e)))$. Hence, the
tree $f(g(f(e,e),e),f(e,g(e,g(e,e))))$ is for instance translated into
$d^{5}(e)$. Clearly, this tree translation is functional and can be realized
by the following functional $att$.

Let $A=(S,I,\Sigma,\Delta,a,R)$ where $S=\\{a,a_{g}\\}$ and
$I=\\{b,b_{g},b_{g}^{\prime}\\}$. For the root marker and the symbol $e$, we
define

$R_{\\#}=\\{b_{g}^{\prime}(\pi 1)\rightarrow e\\}\quad\text{and}\quad
R_{e}=\\{a(\pi)\rightarrow b(\pi),\ a_{g}(\pi)\rightarrow d(b_{g}(\pi)\\},$

respectively. For the symbol $f$, we define

$\begin{array}[]{c lcl c lcl c lcl}R_{f}=\\{&a(\pi)&\rightarrow&a(\pi
2)&&b(\pi 2)&\rightarrow&a(\pi 1)&&b(\pi 1)&\rightarrow&b(\pi)\\\
&a_{g}(\pi)&\rightarrow&d(a_{g}(\pi 2))&&b_{g}(\pi 2)&\rightarrow&a_{g}(\pi
1)&&b_{g}(\pi 1)&\rightarrow&b_{g}(\pi)\\\ &b_{g}^{\prime}(\pi
2)&\rightarrow&b_{g}^{\prime}(\pi)&&b_{g}^{\prime}(\pi
1)&\rightarrow&b_{g}^{\prime}(\pi)\ \\}.\end{array}$

Finally, the rules for the symbol $g$ are given by

$\begin{array}[]{ c lcl c lcl c lcl}R_{g}=\\{&a(\pi)&\rightarrow&d(a_{g}(\pi
2))&&a_{g}(\pi)&\rightarrow&d(a_{g}(\pi 2))&&b_{g}(\pi
2)&\rightarrow&a_{g}(\pi 1)\\\ &b_{g}(\pi 1)&\rightarrow&b_{g}(\pi)&&b_{g}(\pi
1)&\rightarrow&b_{g}^{\prime}(\pi)\ \\}.\\\ \end{array}$

In short, the attributes $a$ and $b$ are used for traversing the input tree in
reverse pre-order until a node labeled by $g$ is found. In the case that such
a node is found, the attributes with subscript $g$ produce the output tree.
Consider in particular, the rules $b_{g}(\pi 1)\rightarrow b_{g}(\pi)$ and
$b_{g}(\pi 1)\rightarrow b_{g}^{\prime}(\pi)$ in $R_{g}$. With these rules,
$A$ guesses whether the node labeled by $g$ that it is currently processing
has a proper ancestor labeled by $g$ or not. In particular, applying the rule
$b_{g}(\pi 1)\rightarrow b_{g}(\pi)$ means that $A$ guesses that such a proper
ancestor exists, while applying $b_{g}(\pi 1)\rightarrow b_{g}^{\prime}(\pi)$
means that $A$ guesses the opposite.

Though the tree translation in Example 2 can by realized by a functional
$att$, no $datt$ $D$ can realize it. In the following, we will explain
(without a formal proof) why this is the case. The key point is that $D$ is
unable to determine for an input tree $s$ and a given node $v$ whether or not
a proper ancestor $v^{\prime}$ of $v$ exists that is also labeled by $g$ _and_
in the case that such a $v^{\prime}$ exists, continue to output symbols
afterwards. To specify this statement consider the following. Obviously, $D$
visits every node for which it has to produce a symbol $d$. W.l.o.g. it can be
assumed that $D$ visits all such nodes in reverse pre-order. Assume that $D$
has already produced an output symbol $d$ for every descendant of the node $v$
and that an attribute of $D$ is currently processing $v$. Now $D$ must
determine whether or not any more symbols $d$ need to be produced. In other
words, $D$ must determine whether or not an ancestor of $v$ is labeled by $g$
or not. To do so $D$ traverses $s$ from $v$ ‘upwards’ using rules of the form
$\beta(\pi j)\rightarrow\beta^{\prime}(\pi)$ where $\beta$ and
$\beta^{\prime}$ are some inherited attributes. Assume that this upwards
traversal yields that a proper ancestor $v^{\prime}$ of $v$ is labeled by $g$.
To realize the tree translation in Example 2, $A$ must produce a symbol $d$
for every descendant of $v^{\prime}$. Now, the question is has $D$ done so for
every descendant of $v^{\prime}$? If not then $D$ needs to determine for which
descendants it still has to produce output (see Figure 2). To do so $D$ needs
to return to the node $v$. However $D$ cannot memorize the node $v$ from which
it started and thus does not know how to return to $v$.

gg$v^{\prime}$$v$ Figure 2:  Since $D$ visits nodes for which it has to
produce an output symbol $d$ in reverse pre-order, $D$ must still produce a
symbol $d$ for every node in the grayed section after determining that the
ancestor $v^{\prime}$ of $v$ is also labeled by $g$.

Even giving $D$ access to look-ahead dos not remedy this problem. Informally,
this is because look-ahead can only provide information about subtrees of $v$.
For the tree translation in Example 2 however, we require to know whether or
not an ancestor of $v$ is labeled by $g$.

Observe that the knowledge whether or not an ancestor of $v$ is labeled by $g$
in Example 2 can be acquired with regular look-around.

###### Example 3

Let $U=(B,T)$ be a look-around where $B$ simply realizes the identity. Let
$T^{\prime}$ contain the rules

$\begin{array}[]{lclclcl}q(f(x_{1},x_{2}))&\rightarrow&f(q(x_{1}),q(x_{2}))&&q^{\prime}(f^{\prime}(x_{1},x_{2}))&\rightarrow&f^{\prime}(q^{\prime}(x_{1}),q^{\prime}(x_{2}))\\\
q(g(x_{1},x_{2}))&\rightarrow&g^{\prime}(q^{\prime}(x_{1}),q^{\prime}(x_{2}))&&q^{\prime}(g^{\prime}(x_{1},x_{2}))&\rightarrow&g^{\prime}(q^{\prime}(x_{1}),q^{\prime}(x_{2}))\\\
q(e)&\rightarrow&e&&q^{\prime}(e^{\prime})&\rightarrow&e^{\prime}\end{array}$

Thus, all nodes $v$ of $s$ that are either labeled by $g$ or are a descendant
of such a node have a prime added to their label by $U$.

It should be clear that a $datt^{U}$ $D$ using the relabeling $U$ in the
previous example can realize the tree translation in Example 2. In particular,
to test whether or not an ancestor of a given node $v$ is labeled by $g$, $D$
simply needs to test whether or not the parent node of $v$ is labeled by a
symbol with a prime.

For completeness, note that the classes of tree translations realized by
functional $att$ and $datt^{R}$ are in fact incomparable as shown in the
following example.

###### Example 4

Consider the following tree translation: Let $L$ be a regular tree language
over $\Sigma$. Let $\Delta$ consists of two symbols ${}^{\prime}y^{\prime}$
and ${}^{\prime}n^{\prime}$ that are both of rank $0$ and let $s\in
T_{\Sigma}$. If $s\in L$ that we translate $s$ into ${}^{\prime}y^{\prime}$
otherwise $s$ is translated into ${}^{\prime}n^{\prime}$. Since $L$ is a
regular tree language, a deterministic bottom-up automaton $B$ accepting $L$
exists. Using $B$ we can construct a $datt$ with look-ahead that realizes the
translation above in a straight-forward manner.

Now consider a nondeterministic functional $att$ $A$. Before $A$ produces any
output, it must check whether its input tree $s$ is an element of $L$ or not.
Specifically, $A$ has to check whether $s\in L$ in a tree-walking-fashion,
i.e., $A$ tests $s$ like a _tree-walking automaton_ would. It is well known
that tree-walking automata do not recognize all regular tree languages [3].
Thus, there are regular tree languages $L$ for which no functional $att$
realizing the above translation exists.

Denote by $\mathcal{F}$ the class all functions. Furthermore, denote by
$ATT^{R}$ and $dATT^{R}$ the classes of tree translations realizable by
nondeterministic $atts^{R}$ and deterministic $atts^{R}$, respectively. Define
$ATT$ and $dATT$ analogously. Examples 2 and 4 yield the following.

###### Proposition 3

The following statements hold:

  1. 1.

$dATT\subsetneq ATT\cap\mathcal{F}$ and $dATT^{R}\subsetneq
ATT^{R}\cap\mathcal{F}$.

  2. 2.

The classes $ATT\cap\mathcal{F}$ and $dATT^{R}$ are incomparable.

##  5 Constructing a Uniformizer for an $\mathbf{Att}$

Recall that before we can prove that for a given functional composition of $n$
$atts^{U}$ an equivalent composition of $n$ $datts^{U}$ can be constructed, we
prove that for a given $att^{U}$ $\hat{A}=(U,A)$, a $datt^{U}$ $\hat{D}$ can
be constructed such that $\tau_{\hat{D}}$ is a uniformizer of
$\tau_{\hat{A}}$. For the latter, we first show how to construct a $datt^{U}$
$D$ that realizes a uniformizer of $\tau_{A}$.

Subsequently, let $A=(S,I,\Sigma,\Delta,a_{0},R)$ be fixed. Note that we allow
the $att$ $A$ to be circular.

Before we construct the $datt^{U}$ $D$, we introduce the following
definitions. Let $s\in\text{dom}(A)$. Let $t_{1},\dots,t_{n}$ be trees in
$T_{\Delta}[\text{SI}(s^{\\#})]$ and let

$\tau=(t_{1}\Rightarrow_{A,s^{\\#}}t_{2}\Rightarrow_{A,s^{\\#}}\cdots\Rightarrow_{A,s^{\\#}}t_{n}).$

We call $\tau$ a _translation of $A$ on input $s$_ if $t_{1}=a_{0}(1)$ and
$t_{n}\in T_{\Delta}$. If $\tau$ is a translation of $A$ on input $s$, then
the _output of $\tau$_ is $t_{n}$. Furthermore, we say that $\tau$ contains a
_productive cycle_ if $i<j\leq n$, a node $u$ and a proper descendant
$u^{\prime}$ of $u$ as well as $\alpha(\nu)\in\text{SI}(s^{\\#})$ exist such
that $t_{i}[u]=t_{j}[u^{\prime}]=\alpha(\nu).$ On the other hand, if
$i<\iota<j$ and a node $u$ exist such that
$t_{i}[u]=t_{j}[u]=\alpha(\nu)\quad\text{but}\quad
t_{\iota}[u]\neq\alpha(\nu),$ then we say that $\tau$ contains a _non-
productive cycle_. We say that $\tau$ is _cycle-free_ if $\tau$ does not
contain a cycle of either type.

###### Observation 1

Let $s\in\text{dom}(A)$. Then a cycle free translation $\tau$ of $A$ on input
$s$ exists.

Note that if $A$ is noncircular then any translation of $A$ on input $s$ is
cycle-free. Let $\tau$ be a cycle-free translation of $A$ on input $s$. Then
clearly, multiple instances of
$\alpha^{\prime}(\nu^{\prime})\in\text{SI}(s^{\\#})$ may occur in $\tau$. This
means that since $A$ is nondeterministic, at distinct instances of
$\alpha^{\prime}(\nu^{\prime})$ distinct rules may be applied. In the
following, we say that $\tau$ is _uniform_ if at all such instances of
$\alpha^{\prime}(\nu^{\prime})$ the same rule is applied. With Observation 1,
it is easy to see that the following holds.

###### Observation 2

Let $s\in\text{dom}(A)$. Then a cycle free translation $\tau$ of $A$ on input
$s$ that is also uniform exists.

###### Example 5

Consider the following $att$ $A=(S,I,\Sigma,\Delta,a,R)$ where
$S=\\{a,a^{\prime}\\}$ and $I=\\{b\\}$. Let
$\Sigma=\\{f^{1},g^{1},h^{1},e^{0}\\}$ and $\Delta=\\{g^{2},g^{\prime
2},h^{1},e^{0}\\}$.

The rules for the root marker a given by $R_{\\#}=\\{b(\pi 1)\rightarrow
a^{\prime}(\pi 1)\\}$ while the rules for the symbol $e$ are given by
$R_{e}=\\{a(\pi)\rightarrow b(\pi),a^{\prime}(\pi)\rightarrow e\\}$.
Additionally, for the symbol $f$, we define

$\begin{array}[]{cc rll c rll c rll c rll}R_{f}&=\\{&a(\pi)&\rightarrow&a(\pi
1)&&a^{\prime}(\pi 1)&\rightarrow&a(\pi
1)&&a^{\prime}(\pi)&\rightarrow&e&&b(\pi 1)&\rightarrow&b(\pi)\ \\}\\\
\end{array}$

while for the symbol $g$, we define

$\begin{array}[]{cc rll c rll c rll }R_{g}&=\\{&a(\pi)&\rightarrow&g(a(\pi
1),a(\pi 1))&&a^{\prime}(\pi 1)&\rightarrow&g(a(\pi 1),a(\pi
1))&&a^{\prime}(\pi)&\rightarrow&e\\\ &&a(\pi)&\rightarrow&g^{\prime}(a(\pi
1),a(\pi 1))&&a^{\prime}(\pi 1)&\rightarrow&g^{\prime}(a(\pi 1),a(\pi
1))&&b(\pi 1)&\rightarrow&b(\pi)\ \\}.\\\ \end{array}$

Finally, for the symbol $h$, we define

$\begin{array}[]{cc rll c rll c rll c rll
}R_{h}&=\\{&a(\pi)&\rightarrow&h(a(\pi 1))&&a^{\prime}(\pi
1)&\rightarrow&h(a(\pi 1))&&a^{\prime}(\pi)&\rightarrow&e&&b(\pi
1)&\rightarrow&b(\pi)\ \\}.\\\ \end{array}$

Consider the trees $s_{1}=f(e)$, $s_{2}=h(e)$ and $s_{3}=g(g(e))$. Consider
the translation

$\begin{array}[]{lllllll
lllll}a(1)&\Rightarrow_{A,s_{1}^{\\#}}&a(1.1)&\Rightarrow_{A,s_{1}^{\\#}}&b(1.1)&\Rightarrow_{A,s_{1}^{\\#}}&b(1)&\Rightarrow_{A,s_{1}^{\\#}}&a^{\prime}(1)\\\
&\Rightarrow_{A,s_{1}^{\\#}}&a(1.1)&\Rightarrow_{A,s_{1}^{\\#}}&b(1.1)&\Rightarrow_{A,s_{1}^{\\#}}&b(1)&\Rightarrow_{A,s_{1}^{\\#}}&a^{\prime}(1)&\Rightarrow_{A,s_{1}^{\\#}}&e\end{array}$

of $A$ on input $s_{1}$. Clearly this translation contains a non-productive
cycle. Analogously, the translation

$\begin{array}[]{lllllll}a(1)&\Rightarrow_{A,s_{2}^{\\#}}&h(a(1.1))&\Rightarrow_{A,s_{2}^{\\#}}&h(b(1.1))&\Rightarrow_{A,s_{2}^{\\#}}&h(b(1))\\\
&\Rightarrow_{A,s_{2}^{\\#}}&h(a^{\prime}(1))&\Rightarrow_{A,s_{2}^{\\#}}&h(h(a(1.1)))&\Rightarrow_{A,s_{2}^{\\#}}&h(h(b(1.1)))\\\
&\Rightarrow_{A,s_{2}^{\\#}}&h(h(b(1)))&\Rightarrow_{A,s_{2}^{\\#}}&a^{\prime}(1)&\Rightarrow_{A,s_{2}^{\\#}}&h(h(e))\end{array}$

of $A$ on input $s_{2}$ contains a productive cycle.

Tress that $s_{3}$ can be translated into include
$t_{1}=g(g(e,e),g^{\prime}(e,e))$,
$t_{2}=g^{\prime}(g^{\prime}(e,e),g^{\prime}(e,e))$ and
$t_{3}=g(g(e,e),g(e,e))$. It can be verified that the translations on input
$s_{3}$ that output these trees are all cycle-free. Note however that the
translation that outputs $t_{1}$ is however not uniform. In particular, two
instances of $a(2)$ occur in this translation and while at one instance of
$a(2)$ the rule $a(\pi)\rightarrow g(a(\pi 1),a(\pi 1))$ is applied, the rule
applied at the the other instance is $a(\pi)\rightarrow g^{\prime}(a(\pi
1),a(\pi 1))$. The translations of $A$ on input $s_{2}$ that output $t_{2}$
and $t_{3}$ on the other hand are uniform.

Subsequently, denote by $\breve{\tau}_{A}$ the set of all pairs
$(s,t)\in\tau_{A}$ for which a uniform translation $\tau$ exists whose input
is $s$ and whose output is $t$. By definition of $\breve{\tau}_{A}$ and due to
Observation 2, it should be clear that the following holds.

###### Lemma 1

$\breve{\tau}_{A}\subseteq\tau_{A}$ and
$\text{dom}(\breve{\tau}_{A})=\text{dom}(\tau_{A})$.

We remark that $\breve{\tau}_{A}$ is not necessarily a uniformizer of
$\tau_{A}$ because $\breve{\tau}_{A}$ is not necessarily a function.

In the following, we construct a $datt^{U}$ $D$ that realizes a uniformizer of
$\tau_{A}$ on the basis of uniform translations. More precisely, to construct
$D$ we proceed as follows; First, we show that given $A$, a nondeterministic
top-down relabeling $T$ and a $datt$ $D^{\prime}$ can be constructed such that
the composition of $T$ and $D^{\prime}$ simulates all uniform translations of
$A$. In particular, denote by $\tau_{C}$ the tree translation realized by the
composition of $T$ and $D^{\prime}$, that is,

$\tau_{C}=\\{(s,t)\mid(s,s^{\prime})\in\tau_{T}\text{ and
}(s^{\prime},t)\in\tau_{D^{\prime}}\\}.$

We can construct $T$ and $D^{\prime}$ such that $\tau_{C}=\breve{\tau}_{A}$.
Given $T$ and $D^{\prime}$, we show how to construct a $datt^{U}$ $D$ such
that $D$ realizes a uniformizer of $\tau_{C}$. Due to Lemma 1, it follows that
the $datt^{U}$ $D$ also realizes a uniformizer of $\tau_{A}$.

Before constructing $T$ as well as $D^{\prime}$ we introduce the following
definition. Consider the set $R_{\sigma}$, i.e., the set of all rules of $A$
for the symbol $\sigma$. Let $\bar{R}\subseteq R_{\sigma}$. We call the set
$\bar{R}$ _unambiguous_ if $\bar{R}$ does not contain two distinct rules with
the same left-hand side.

Idea of $\mathbf{T}$ and $\mathbf{D^{\prime}}$. In the following we describe
our idea: To simulate uniform translations of $A$, the nondeterministic top-
down relabeling $T$ determines for every input node $v$ which rules will be
used at the node $v$. The $datt$ $D$ then only has to apply these rules.

More precisely, denote by $\tilde{\Sigma}$ the output alphabet of $T$ and the
input alphabet of $D^{\prime}$. The alphabet $\tilde{\Sigma}$ consists of
symbols of the form $\langle\sigma,\bar{R}\rangle$ where $\sigma\in\Sigma$ and
$\bar{R}$ is an unambiguous subset of $R_{\sigma}$. The symbol
$\langle\sigma,\bar{R}\rangle$ is of rank $k$ if $\sigma$ is. By relabeling a
node by $\langle\sigma,\bar{R}\rangle$, $T$ signals to $D^{\prime}$ that only
rules in $\bar{R}$ are allowed to be used at that node. Note that since
$\bar{R}$ is an unambiguous subset of $R_{\sigma}$, it follows easily that if
$(s,\tilde{s})\in\tau_{T}$ and $\tau^{\prime}$ is a translation of
$D^{\prime}$ on input $\tilde{s}$, then $\tau^{\prime}$ simulates a
translation $\tau$ of $A$ on input $s$ that is uniform.

Construction of $\mathbf{T}$. Subsequently, we define the nondeterministic
top-down relabeling $T=(\\{q\\},\emptyset,\Sigma,\tilde{\Sigma},q,\tilde{R})$.
To do so, all we need to do is to define the set $\tilde{R}$. Specifically, we
define that

$q(\sigma(x_{1},\dots,x_{k}))\rightarrow\langle\sigma,\bar{R}\rangle(q(x_{1}),\dots,q(x_{k}))\in\tilde{R}$

for all $\sigma\in\Sigma_{k}$, $k\geq 0$ and for all unambiguous
$\bar{R}\subseteq R_{\sigma}$.

Construction of $\mathbf{D^{\prime}}$. The $datt$ $D^{\prime}$ is constructed
in a straight-forward manner. In particular, we define
$D^{\prime}=(S,I,\tilde{\Sigma},\Delta,a_{0},R^{\prime})$.

Recall that due to Proposition 1, we can assume that $R_{\\#}$ is
deterministic, i.e., the set of rules of $A$ for the root marker, contains no
distinct rules with the same left-hand side. In other words, we can assume
that $R_{\\#}$ is unambiguous. Therefore, we define
$R^{\prime}_{\\#}=R_{\\#}$.

Recall that $\tilde{\Sigma}$ consists of symbols of the form
$\langle\sigma,\bar{R}\rangle$ where $\sigma\in\Sigma$ and $\bar{R}$ is an
unambiguous subset of $R_{\sigma}$. For the symbol
$\langle\sigma,\bar{R}\rangle$ we define
$R^{\prime}_{\langle\sigma,\bar{R}\rangle}=\bar{R}$. Since by definition of
the alphabet $\bar{\Sigma}$, the set $\bar{R}$ is unambiguous it should be
clear that $D^{\prime}$ is deterministic.

###### Example 6

Consider the $att$ $A$ in Example 5. Consider the symbol $f$ and the set of
rules $R_{f}$ of $A$. Then the unambiguous subsets of $R_{f}$ are

$\begin{array}[]{l c l}\\{a(\pi)\rightarrow a(\pi 1),\ b(\pi 1)\rightarrow
b(\pi),\ a^{\prime}(\pi 1)\rightarrow a(\pi 1)\\}&&\\{b(\pi 1)\rightarrow
b(\pi),\ a^{\prime}(\pi 1)\rightarrow e\\}\\\ \\{a(\pi)\rightarrow a(\pi 1),\
b(\pi 1)\rightarrow b(\pi),\ a^{\prime}(\pi 1)\rightarrow
e\\}&&\\{a(\pi)\rightarrow a(\pi 1)\\}\\\ \\{a(\pi)\rightarrow a(\pi 1),\
a^{\prime}(\pi 1)\rightarrow a(\pi 1)\\}&&\\{a^{\prime}(\pi)\rightarrow
e\\}\\\ \\{a(\pi)\rightarrow a(\pi 1),\ a^{\prime}(\pi 1)\rightarrow
e\\}&&\\{a^{\prime}(\pi 1)\rightarrow a(\pi 1)\\}\\\ \\{a(\pi)\rightarrow
a(\pi 1),\ b(\pi 1)\rightarrow b(\pi)\\}&&\\{b(\pi 1)\rightarrow b(\pi)\\}\\\
\\{b(\pi 1)\rightarrow b(\pi),\ a^{\prime}(\pi 1)\rightarrow a(\pi
1)\\}&&\emptyset.\end{array}$

To construct the nondeterministic top-down relabeling
$T=(\\{q\\},\emptyset,\Sigma,\tilde{\Sigma},q,\tilde{R})$ from $A$, we define
for each of these subsets $\bar{R}$ an output symbol of the form $\langle
f,\bar{R}\rangle$ and a rule of the form $q(f(x_{1}))\rightarrow\langle
f,\bar{R}\rangle(q(x_{1}))$. For instance for the sets $\\{a(\pi)\rightarrow
a(\pi 1),\ b(\pi 1)\rightarrow b(\pi)\\}$ and $\\{a(\pi)\rightarrow a(\pi
1)\\}$, we define the symbols

$\langle f,\\{a(\pi)\rightarrow a(\pi 1),\ b(\pi 1)\rightarrow
b(\pi)\\}\rangle\quad\text{and}\quad\langle f,\\{a(\pi)\rightarrow a(\pi
1)\\}\rangle$

along with the rules

$q(f(x_{1}))\rightarrow\langle f,\\{a(\pi)\rightarrow a(\pi 1),\ b(\pi
1)\rightarrow b(\pi)\\}\rangle(q(x_{1}))$

and

$q(f(x_{1}))\rightarrow\langle f,\\{a(\pi)\rightarrow a(\pi
1)\\}\rangle(q(x_{1})),$

respectively. For the rule sets $R_{g}$, $R_{h}$ and $R_{e}$ of $A$, we
proceed analogously.

To construct of the $datt$
$D^{\prime}=(S,I,\tilde{\Sigma},\Delta,a_{0},R^{\prime})$ from $A$, we define
for the output symbols $\langle f,\\{a(\pi)\rightarrow a(\pi 1),\ b(\pi
1)\rightarrow b(\pi)\\}\rangle$ and $\langle f,\\{a(\pi)\rightarrow a(\pi
1)\\}\rangle$ of $T$ for example, the rule sets

$R^{\prime}_{\langle f,\\{a(\pi)\rightarrow a(\pi 1),\ b(\pi 1)\rightarrow
b(\pi)\\}\rangle}=\\{a(\pi)\rightarrow a(\pi 1),\ b(\pi 1)\rightarrow
b(\pi)\\}$

and

$R^{\prime}_{\langle f,\\{a(\pi)\rightarrow a(\pi
1)\\}\rangle}=\\{a(\pi)\rightarrow a(\pi 1)\\},$

respectively. We proceed analogously for the remaining output symbols. Note
that $R^{\prime}_{\\#}=R_{\\#}$.

Recall that $\tau_{C}$ denotes the tree translation realized by the
composition of $T$ and $D^{\prime}$ and that $\breve{\tau}_{A}$ is the set of
all pairs $(s,t)\in\tau_{A}$ for which there is a a uniform translation. We
now prove the following statement.

###### Lemma 2

The sets $\breve{\tau}_{A}$ and $\tau_{C}$ are equal.

###### Proof

To begin our proof we show that $\tau_{C}\subseteq\breve{\tau}_{A}$. Let
$(s,\tilde{s})\in\tau_{T}$ and let $(\tilde{s},t)\in\tau_{D^{\prime}}$. Let

$a_{0}(1)=t_{1}\Rightarrow_{D^{\prime},\tilde{s}^{\\#}}t_{2}\Rightarrow_{D^{\prime},\tilde{s}^{\\#}}\cdots\Rightarrow_{D^{\prime},\tilde{s}^{\\#}}t_{n}=t$

be the corresponding translation of $D^{\prime}$ on input $\tilde{s}$. Let
$\langle\sigma,\bar{R}\rangle$ be an arbitrary symbol in $\tilde{\Sigma}$.
Recall that this means that $\sigma\in\Sigma$ and $\bar{R}$ is an unambiguous
subset of $R_{\sigma}$. By construction of $D^{\prime}$,
$R^{\prime}_{\langle\sigma,\bar{R}\rangle}\subseteq R_{\sigma}$. Hence, a
translation $\tau$ of $A$ on input $s$ exists that is of the form

$\tau=(a_{0}(1)=t_{1}\Rightarrow_{A,s^{\\#}}t_{2}\Rightarrow_{A,s^{\\#}}\cdots\Rightarrow_{A,s^{\\#}}t_{n}=t)$

Since $D^{\prime}$ is deterministic, $\tau$ is a uniform translation.

To show the converse, that is, to show that
$\tau_{C}\supseteq\breve{\tau}_{A}$, consider a uniform translation

$\tau=(a_{0}(1)=t_{1}\Rightarrow_{A,s^{\\#}}t_{2}\Rightarrow_{A,s^{\\#}}\cdots\Rightarrow_{A,s^{\\#}}t_{n}=t)$

of $A$ on input $s\in T_{\Sigma}$. Let $v\in V(s)$ and let
$s[v]=\sigma\in\Sigma_{k}$, $k\geq 0$. Let $a\in S$ and
$a(\pi)\rightarrow\xi\in R_{\Sigma}$. Recall that for a right-hand side $\xi$
of a rule in $R_{\sigma}$ and a node $v$, $\xi[\pi\leftarrow v]$ denotes the
tree obtained by replacing all occurrences of $\pi$ by $v$ (cf. Section 2).

In the following, we say that the rule $a(\pi)\rightarrow\xi$ is _used in
$\tau$ at the input node $v$_ if $i\in[n]$ and a node $u\in V(t_{i})$ exist
such that $t_{i}[u]=a(1.v)$ and $t_{i+1}=t_{i}[u\leftarrow\xi[\pi\leftarrow
1.v]]$.

Analogously, we say that the rule $b(\pi j)\rightarrow\xi$, where $b\in I$ and
$k\in[k]$, is _used in $\tau$ at the input node $v$_ if $i\in[n]$ and a node
$u\in V(t_{i})$ exist such that $t_{i}[u]=b(1.v.j)$ and
$t_{i+1}=t_{i}[u\leftarrow\xi[\pi\leftarrow 1.v]]$.

Note that the reason why we have $a(1.v)$ and $b(1.v.j)$ in the definitions
above is because translations of $A$ always involve the root marker.

Denote by $\tau[v]$ the set of all rules used in $\tau$ at the input node $v$.
Note that since $\tau$ is a uniform translation, $\tau[v]$ is an unambiguous
subset of $R_{\sigma}$. By construction of $T$, it should be clear that $T$
can transform the tree $s$ into the tree $\tilde{s}$ over $\tilde{\Sigma}$
such that if the node $v$ is labeled by the symbol $\sigma$ in $s$ then $v$ is
labeled by $\langle\sigma,\tau[v]\rangle$ in $\tilde{s}$. By definition of
$D^{\prime}$ it follows that there is a translation of $D^{\prime}$ on input
$\tilde{s}$ that outputs $t$. Hence, our lemma follows.

Before we construct the $datt^{U}$ $D=(U,D^{\prime})$ from $T$ and
$D^{\prime}$, note that we can assume that
$\text{range}(T)\subseteq\text{dom}(D^{\prime})$. This is because by
Proposition 2 (see also [11]), the domain of the $datt$ $D^{\prime}$ is
effectively regular. Hence a (nondeterministic) top-down automaton $M$
recognizing $D^{\prime}$ exists. In order to restrict the range of $T$ to the
domain of $D^{\prime}$, we simply run $M$ in parallel with $T$ in the usual
way, that is, we construct a new top-down relabeling from $T$ and $M$ using
the product construction (cf [1, Definition on p.195]).

Furthermore, note by [6], that the following holds for top-down tree
transducers, i.e., $att$ without inherited attributes.

###### Proposition 4

For any top-down tree transducer $M$, a deterministic top-down tree transducer
$M^{\prime}$ with regular-look-ahead can be constructed such that $M^{\prime}$
realizes a uniformizer of $\tau_{M}$.

###### Proof

Subsequently we briefly sketch the idea of the procedure given in [6].
Consider the top-down tree transducer $M$. Denote by $\Sigma$ and $\Delta$ the
input and output alphabet of $M$, respectively. Let $R$ be the set of rules of
$M$ Assume a total order on the rules in $R$.

Given $M$, we construct $M^{\prime}$ such that $M^{\prime}$ has the same
states as $M$. With theses states $M^{\prime}$ simulates $M$ as follows: Let
the state $q$ process a node labeled by $\sigma\in\Sigma$. Let
$\rho_{1},\dots,\rho_{n}$ be the rules of $M$ for the symbol $\sigma$ where
$q$ occurs on the left-hand side. To simulate $M$, $M^{\prime}$ checks which
of the rules $\rho_{1},\dots,\rho_{n}$ is _applicable_ , that is, which of
these rules lead to the generation of a ground output tree (i.e., a tree in
$T_{\Delta}$). Whether or not a rule is applicable can be tested by
$M^{\prime}$ using its look-ahead. Among the applicable rules, $M^{\prime}$
then picks the first one according to the given total order on $R$ to simulate
$M$.

Note that if $M$ is a top-down relabeling, then the top-down tree transducer
$M^{\prime}$ with regular-look-ahead that the procedure in [6] yields is in
fact a top-down relabeling with regular-look-ahead, i.e., a look-around.

Construction of the $\mathbf{datt^{U}\ D=(U,D^{\prime})}$. To construct the
$datt^{U}$ $D$, all we need to do is to construct $U$ from $T$. Note that by
definition, $T$ is also a top-down tree transducer. Therefore, due to
Proposition 4, let $U$ be constructed as one of the top-down tree transducers
with regular-look-ahead that realizes a uniformizer of $\tau_{T}$. Since $T$
is a top-down relabeling, previous observations yield that $U$ is a look-
around. This concludes the construction of the $datt^{U}$ $D$.

###### Example 7

Consider the nondeterministic top-down relabeling $T$ and the $datt$
$D^{\prime}$ in Example 6. It can be verified that the domain of $D^{\prime}$
consists of trees $s$ for which the following statements hold:

  1. 1.

Let $v$ be the root of $s$. Then $v$ is either labeled by

    1. (a)

$\langle e,R_{e}\rangle$ or

    2. (b)

by a symbol of the form $\langle\sigma,\bar{R}\rangle$, where
$\sigma\in\\{f,g,h\\}$. The set $\bar{R}$ is a subset of $R_{\sigma}$ that
contains the rule $a^{\prime}\rightarrow e$ as well as a rule in which
$a(\pi)$ occurs on the left-hand side and a rule in which $b(\pi 1)$ occurs on
the left-hand side.

  2. 2.

All other nodes $v^{\prime}$ of $s$, are either labeled by

    1. (a)

$\langle e,\bar{R}^{\prime}\rangle$ where $\bar{R}$ is a subset of $R_{e}$
that contains the rule $a(\pi)\rightarrow\b{(}\pi)$ or

    2. (b)

by a symbol of the form $\langle\sigma,\bar{R}\rangle$, where
$\sigma\in\\{f,g,h\\}$ and the set $\bar{R}$ is a subset of $R_{\sigma}$ that
contains a rule in which $a(\pi)$ occurs on the left-hand side and a rule in
which $b(\pi 1)$ occurs on the left-hand side.

It is easy to see that the rules of $T$ can be modified such that $T$ only
outputs trees for which the previous statements hold.

Recall that by [6], Proposition 4 holds. Hence, top-down tree transducer with
regular-look-ahead that realizes a uniformizer of $\tau_{T}$. In fact one of
the possible top-down tree transducer with regular-look-ahead that the
procedure of [6] yields is $U=(B,T^{\prime})$ where $B$ is realizes the
identity and
$T^{\prime}=(\\{q_{0},q\\},\emptyset,\Sigma,\tilde{\Sigma},q_{0},\tilde{R}^{\prime})$.
The set $\tilde{R}^{\prime}$ contains the rules

$\begin{array}[]{cll c cll}q_{0}(f(x_{1}))&\rightarrow&\langle
f,\bar{R}_{f}\rangle(q(x_{1}))&&q_{0}(g(x_{1}))&\rightarrow&\langle
g,\bar{R}_{g}\rangle(q(x_{1}))\\\ q_{0}(h(x_{1}))&\rightarrow&\langle
h,\bar{R}_{h}\rangle(q(x_{1}))&&q_{0}(e)&\rightarrow&\langle
e,\bar{R}_{e}\rangle(q(x_{1}))\\\ \end{array}$

along with the rules

$\begin{array}[]{cll c cll}q(f(x_{1}))&\rightarrow&\langle
f,\bar{R}_{f}\rangle(q(x_{1}))&&q(g(x_{1}))&\rightarrow&\langle
g,\bar{R}_{g}\rangle(q(x_{1}))\\\ q(h(x_{1}))&\rightarrow&\langle
h,\bar{R}_{h}\rangle(q(x_{1}))&&q(e)&\rightarrow&\langle
e,\bar{R}_{e}\rangle(q(x_{1}))\\\ \end{array}$

where

  * •

$\bar{R}_{f}=\\{a_{\pi}(\pi)\rightarrow e,a(\pi)\rightarrow a(\pi 1),\ b(\pi
1)\rightarrow b(\pi)\\}$,

  * •

$\bar{R}_{g}=\\{a_{\pi}(\pi)\rightarrow e,a_{\pi}(\pi)\rightarrow e,\
a(\pi)\rightarrow g^{\prime}(a(\pi 1),a(\pi 1)),\ b(\pi 1)\rightarrow
b(\pi)\\}$,

  * •

$\bar{R}_{h}=\\{a_{\pi}(\pi)\rightarrow e,\ a(\pi)\rightarrow h(a(\pi 1)),\
b(\pi 1)\rightarrow b(\pi)\\}$, and

  * •

$\bar{R}_{e}=\\{a_{\pi}(\pi)\rightarrow e,a(\pi)\rightarrow b(\pi)\\}$.

Note that $U$ is a look-around. Hence, together with $D^{\prime}$, $U$ yields
a $datt^{U}$ that realizes a unifomizer of $\tau_{A}$.

###### Lemma 3

The $datt^{U}$ $D=(U,D^{\prime})$ realizes a uniformizer of $\tau_{A}$.

###### Proof

Due to Lemmas 1 and 2, it is obviously sufficient to show that $D$ realizes a
uniformizer of $\tau_{C}$. To start with, note that obviously $\tau_{D}$ is a
function since $D$ is deterministic.

By construction of $D$, it follows obviously that $\tau_{D}\subseteq\tau_{C}$.
In particular, this follows since by construction $U$ realizes a uniformizer
of $\tau_{T}$ and hence $\tau_{U}\subseteq\tau_{T}$.

We now show that $\text{dom}(\tau_{C})=\text{dom}(D)$. First note that
$\tau_{D}\subseteq\tau_{C}$ implies
$\text{dom}(\tau_{C})\subseteq\text{dom}(D)$. For the converse, let
$s\in\text{dom}(\tau_{C})$. Obviously, this means that $s\in\text{dom}(T)$.
Since $U$ realizes a uniformizer of $\tau_{T}$, it has the same domain as
$\tau_{T}$. Therefore, it follows that $s\in\text{dom}(U)$. Let
$(s,\tilde{s})\in\tau_{U}$. Recall our previous assumption that
$\text{range}(T)\subseteq\text{dom}(D^{\prime})$. Obviously, this means that
$\text{range}(U)\subseteq\text{dom}(D^{\prime})$ and hence
$\tilde{s}\in\text{dom}(D^{\prime})$. This in turn yields that
$s\in\text{dom}(D)$ and hence $\text{dom}(\tau_{C})=\text{dom}(D)$.

Due to Lemma 3, the following holds.

###### Theorem 5.1

For any $att$ $A$ a $datt^{U}$ $D$ can be constructed such that $D$ realizes a
uniformizer of $\tau_{A}$.

##  6 From Unformizers for $\mathbf{Att}$ to Uniformizers for
$\mathbf{Att^{U}}$

Consider an arbitrary $att^{U}$ $\hat{A}=(U,A)$. In the following, we show how
to construct a $datt^{U}$ $\hat{D}$ such that $\tau_{\hat{D}}$ is a
uniformizer of $\tau_{\hat{A}}$. Consider the underlying $att$ $A$ of
$\hat{A}$. Due to Theorem 5.1, a $datt^{U}$ $\hat{D}^{\prime}=(U^{\prime},D)$
that realizes a uniformizer of $\tau_{A}$ can be constructed. Clearly

$\begin{array}[]{cl}&\\{(s,t)\mid(s,\breve{s})\in\tau_{U}\text{ and
}(\breve{s},t)\in\tau_{\hat{D}^{\prime}}\\}\\\
=&\\{(s,t)\mid(s,\breve{s})\in\tau_{U}\text{ and
}(\breve{s},\hat{s})\in\tau_{U^{\prime}}\text{ and
}(\hat{s},t)\in\tau_{D}\\}\end{array}$

is a uniformizer of $\tau_{\hat{A}}$. Consider the look-arounds $U$ and
$U^{\prime}$. Due to Theorem 2.6 of [5] and Theorem 1 of [1] (and their
proofs), look-arounds are closed under composition. In other words, a look-
around $\hat{U}$ can be constructed such that

$\tau_{\hat{U}}=\\{(s,\hat{s})\mid(s,\breve{s})\in\tau_{U}\text{ and
}(\breve{s},\hat{s})\in\tau_{U^{\prime}}\\}.$

Therefore, the $datt^{U}$ $(\hat{U},D)$ realizes a uniformizer of
$\tau_{\hat{A}}$. This yields the following.

###### Theorem 6.1

For any $att^{U}$ $\hat{A}$ a $datt^{U}$ that realizes a uniformizer of
$\tau_{\hat{A}}$ can be constructed.

##  7 Final Results

Analogously as in [6] for top-down tree transducers, we obtain the following
result using uniformizers.

###### Theorem 7.1

Let $C$ be a composition of $n$ $atts^{U}$. Then $datts^{U}$
$D_{1},\dots,D_{n}$ can be constructed such that $C$ and the composition of
$D_{1},\dots,D_{n}$ are equivalent.

###### Proof

Consider the $atts^{U}$ $A_{1},\dots,A_{n}$. Let the composition $C$ of
$A_{1},\dots,A_{n}$ be functional, i.e., let

$\tau_{C}=\\{(s,t)\mid(s,t_{1})\in\tau_{A_{1}},(t_{i-1},t_{1})\in\tau_{A_{i}}\text{
for }1<i<n\text{ and }(t_{n-1},t)\in\tau_{A_{n}}\\}$

be a function. For $i<n$, we can assume that
$\text{range}(A_{i})\subseteq\text{dom}(A_{i+1})$ holds. In particular, by
Proposition 2, $\text{dom}(A_{i+1})$ is effectively recognizable, i.e., a
(nondeterministic) top-down automaton $M_{A_{i+1}}$ recognizing
$\text{dom}(A_{i+1})$ can be constructed. By running $M_{A_{i+1}}$ in parallel
to $A_{i}$, it should be clear that we can restrict the range of $A_{i}$ to
trees in $\text{dom}(A_{i+1})$.

By Theorem 6.1, let $D_{1},\dots,D_{n}$ be $datts^{U}$ realizing uniformizers
of $\tau_{A_{1}},\dots,\tau_{A_{n}}$, respectively. Denote by $C_{d}$ the
composition of $D_{1},\dots,D_{n}$. Obviously $\tau_{C_{d}}\subseteq\tau_{C}$.
Note that $\text{range}(A_{i})\subseteq\text{dom}(A_{i+1})$ implies
$\text{range}(D_{i})\subseteq\text{dom}(D_{i+1})$ for $i<n$. In particular,
since $D_{i}$ and $D_{i+1}$ realize uniformizers of $A_{i}$ and $A_{i+1}$,
respectively,

$\text{range}(D_{i})\subseteq\text{range}(A_{i})\subseteq\text{dom}(A_{i+1})=\text{dom}(D_{i+1}).$

Note that $\text{dom}(D_{1})=\text{dom}(A_{1})$. Thus the fact that
$\text{range}(D_{i})\subseteq\text{dom}(D_{i+1})$ for $i<n$, yields that
$C_{d}$ and $C$ have the same domain.

Since $\tau_{C}$ is a function and $\tau_{C_{d}}\subseteq\tau_{C}$, the latter
yields that $\tau_{C_{d}}=\tau_{C}$ which in turn yields Theorem 7.1.

Denote by $(ATT^{U})^{n}$ and $(dATT^{U})^{n}$ the classes of tree
translations realizable by the composition of $n$ nondeterministic $atts^{U}$
and $n$ deterministic $atts^{U}$, respectively. Theorem 7.1 yields the
following.

###### Theorem 7.2

$(ATT^{U})^{n}\cap\mathcal{F}=(dATT^{U})^{n}$.

Note that if an $att$ $A$ (with or without look-around) is functional, then
any $datt^{U}$ that realizes a uniformizer of $\tau_{A}$ is in fact equivalent
to $A$. Hence, Theorems 5.1 and 6.1 yield the following

###### Corollary 1

For any functional $att$ (with or without look-around) an equivalent
$datt^{U}$ can be constructed.

##  8 Conclusion

Consider an arbitrary composition $C$ of $n$ attributed tree transducer with
look-around that realizes a function. In this paper we have provided a
procedure which given $C$, computes $n$ deterministic attributed tree
transducer with look-around $D_{1},\dots,D_{n}$ such that $C$ and the
composition of $D_{1},\dots,D_{n}$ are equivalent. To do so we have shown that
any attributed tree transducer $A$ admits a uniformizer realized a
deterministic attributed tree transducer with look-around can be constructed.
An obvious question is: Do we always need look-around? One wonders when a
uniformizer of $A$ can be implemented by a deterministic attributed tree
transducer _without_ look-around? This question is addressed in [9] for
finite-valued string transducers. Specifically, for such transducers it is
decidable whether or not a uniformizer realized by a deterministic string
transducer exists.

Given our result another question is: Given a composition of attributed tree
transducer $C$ is it decidable whether or not $C$ realizes a function? To the
best of our knowledge this is an open problem. Note that whether or not a
composition of top-down tree transducers is functional has recently been shown
to be decidable [17]. In contrast, even for a single attributed tree
transducer it is unknown whether or not functionality is decidable. Note that
decidability of the latter would imply that equivalence of deterministic
attributed tree transducers is decidable. The latter is a long standing open
problem.

## References

  * [1] Baker, B.S.: Tree transducers and tree languages. Inf. Control. 37(3), 241–266 (1978)
  * [2] Bloem, R., Engelfriet, J.: A comparison of tree transductions defined by monadic second order logic and by attribute grammars. JCSS 61(1), 1–50 (2000)
  * [3] Bojanczyk, M., Colcombet, T.: Tree-walking automata do not recognize all regular languages. SIAM J. Comput. 38(2), 658–701 (2008)
  * [4] Carayol, A., Löding, C.: Uniformization in automata theory. In: Congress of Logic, Methodology and Philosophy of ScienceLogic, Nancy, July 19-26, 2011. p. 153–178. London: College Publications (2014)
  * [5] Engelfriet, J.: Top-down tree transducers with regular look-ahead. Math. Syst. Theory 10, 289–303 (1977)
  * [6] Engelfriet, J.: On tree transducers for partial functions. Inf. Process. Lett. 7(4), 170–172 (1978)
  * [7] Engelfriet, J., Hoogeboom, H.J.: Mso definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Log. 2, 216–254 (1999)
  * [8] Engelfriet, J., Inaba, K., Maneth, S.: Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity. Acta Informatica 58(1-2), 95–152 (2021)
  * [9] Filiot, E., Jecker, I., Löding, C., Winter, S.: On equivalence and uniformisation problems for finite transducers. In: ICALP 2016, July 11-15, 2016, Rome, Italy. LIPIcs, vol. 55, pp. 125:1–125:14. Schloss Dagstuhl (2016)
  * [10] Fülöp, Z.: On attributed tree transducers. Acta Cybern. 5(3), 261–279 (1981)
  * [11] Fülöp, Z., Maneth, S.: Domains of partial attributed tree transducers. Inf. Process. Lett. 73(5-6), 175–180 (2000)
  * [12] Fülöp, Z., Vágvölgyi, S.: Attributed tree transducers cannot induce all deterministic bottom-up tree transformations. Inf. Comput. 116(2), 231–240 (1995)
  * [13] Fülöp, Z., Vogler, H.: Syntax-Directed Semantics - Formal Models Based on Tree Transducers. Monographs in Theoretical Computer Science. An EATCS Series, Springer (1998)
  * [14] Hashimoto, K., Maneth, S.: Characterizing attributed tree translations in terms of macro tree transducers. Theor. Comput. Sci. 963, 113943 (2023)
  * [15] Knuth, D.E.: Semantics of context-free languages. Math. Syst. Theory 2(2), 127–145 (1968), errata in: [16]
  * [16] Knuth, D.E.: Correction: Semantics of context-free languages. Math. Syst. Theory 5(1), 95–96 (1971)
  * [17] Maneth, S., Seidl, H., Vu, M.: Functionality of compositions of top-down tree transducers is decidable. Inf. Comput. 296, 105131 (2024)
  * [18] Maneth, S., Vu, M.: Deciding whether an attributed translation can be realized by a top-down transducer. CoRR abs/2306.04326 (2024), https://arxiv.org/abs/2306.04326v3
  * [19] de Souza, R.: Uniformisation of two-way transducers. In: LATA. Lecture Notes in Computer Science, vol. 7810, pp. 547–558. Springer (2013)