Affiliations: Institut für Informatik, Universität Leipzig, D-04109 Leipzig, Germany. {droste, dheusel}@informatik.uni-leipzig.de
Note: [] Partially supported by DFG Graduiertenkolleg 1763 (QuantLA). Address for correspondence: Institut für Informatik, Universität Leipzig, D-04109 Leipzig, Germany
Abstract: We investigate the supports of weighted unranked tree automata. Our main result states that the support of a weighted unranked tree automaton over a zero-sum free, commutative strong bimonoid is recognizable. For this, we use methods of Kirsten (DLT 2009), in particular, his construction of finite automata recognizing the supports of weighted automata on strings over zero-sum free, commutative semirings. We also get an effective construction of a finite tree automaton recognizing the support of a given weighted unranked tree automaton for zero-sum free, commutative strong bimonoids where Kirsten's zero generation problem is decidable. In addition, we give a translation of nested weighted automata into weighted unranked tree automata for arbitrary commutative strong bimonoids. As a consequence, we derive analogous results for the supports of nested weighted automata. Finally, we give similar results for the supports of weighted pushdown automata.
