AIB 2008-05: An Automata Theoretic Approach to the Theory of Rational Tree Relations

The following technical report is available from
http://aib.informatik.rwth-aachen.de:

An Automata Theoretic Approach to the Theory of Rational Tree Relations
Frank G. Radmacher
AIB 2008-05

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.

.