@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.}
}