@TechReport{Radmacher08,
author = {Frank~G.\ Radmacher},
title = {An Automata Theoretic Approach to the Theory of
Rational Tree Relations},
institution = {RWTH Aachen},
number = {AIB-2008-05},
year = 2008,
month = mar,
url = {http://aib.informatik.rwth-aachen.de/2008/2008-05.ps.gz},
keywords = {tree automata, rational tree relations, transductions},
abstract = {We investigate rational relations over trees.
Our starting point is the definition of rational tree relations via
rational expressions by Raoult (Bull.\,Belg.\,Math.\,Soc.\ 1997).
We develop a new class of automata, called asynchronous tree automata,
which recognize exactly these relations.
The automata theoretic approach is convenient for the solution of
algorithmic problems (like the emptiness problem).
The second contribution of this paper is a new subclass of the rational
tree relations, called separate-rational tree relations, defined via a
natural restriction on asynchronous tree automata. These relations are
closed under composition, preserve regular tree languages, and generate
precisely the regular sets in the unary case (all these properties fail
for the general model), and they are still more powerful than, for
instance, the automatic tree relations.}
}