Affiliations: Department of Computing Science, Umeå
University S-90187 Umeå, Sweden | International Computer Science Institute, 1947 Center
Street, Suite 600 CA-94704 Berkeley, USA | Faculty of Computer Science, Technische
Universität Dresden D-01062 Dresden, Germany
Note: [] Address for correspondence: Faculty of Computer Science,
Technische Universität Dresden, D-01062 Dresden, Germany
Abstract: Several models of automata are available that operate unranked
trees. Two well-known examples are the stepwise unranked tree automaton (suta)
and the parallel unranked tree automaton (puta). By adding a weight, taken from
some semiring, to every transition we generalise these two qualitative automata
models to quantitative models, thereby obtaining weighted stepwise unranked
tree automata (wsuta) and weighted parallel unranked tree automata (wputa); the
qualitative automata models are reobtained by choosing the BOOLEAN semiring.
The weighted versions have applications in natural language processing,
XML-based data management and quantitative information retrieval. We address
the minimisation problem of wsuta and wputa by using (forward and backward)
bisimulations and we prove the following results: (1) for every wsuta an
equivalent forward (resp. backward) bisimulation minimal wsuta can be computed
in time O(mn) where n is the number of states and m is the number of
transitions of the given wsuta; (2) the same result is proved for wputa instead
of wsuta; (3) if the semiring is additive cancellative or the BOOLEAN semiring,
then the bound can be improved to O(mlog n) for both wsuta and wputa; (4) for
every deterministic puta we can compute a minimal equivalent deterministic puta
in time O(mlog n); (5) the automata models wsuta, wputa, and weighted unranked
tree automaton have the same computational power.
Keywords: bisimulation, minimisation, automata, unranked trees
