The supports of weighted unranked tree automata (Q2805397)

In this paper, the authors consider the supports of weighted unranked tree automata over certain bimonoids. A bimonoid \((K,+,\cdot,0,1)\) consists of two monoids \((K,+,0)\) and \((K,\cdot,1)\). It is strong if + is commutative and \(x\cdot 0 = 0 \cdot x = 0\) for every \(x\in K\), it is commutative if the product operation is commutative, and it is zero-sum-free if \(x+y = 0\) implies \(x=y=0\). The support of a weighted tree automaton is the set of all trees that are evaluated to a non-zero element. The main theorem of the paper states that the support of a weighted unranked tree automaton over a zero-sum-free commutative strong bimonoid is recognizable, and that one can construct a finite tree recognizer for it if the bimonoid satisfies a certain condition. The proof and the construction utilize ideas of \textit{D. Kirsten} [Acta Cybern. 20, No. 2, 211--221 (2011; Zbl 1265.68103)], who presented similar results for weighted string automata over zero-sum-free commutative semirings. By giving a translation of weighted nested automata to weighted unranked tree automata, the authors obtain an analog of their main theorem for weighted nested automata. Finally, they present similar results for weighted pushdown automata.