Weighted logics for unranked tree automata (Q2429720)

Generalizing similar work on weighted string and tree languages, on the one hand, and work on unranked tree languages, on the other hand, the authors introduce weighted tree automata and a weighted monadic second-order (MSO) logic for unranked trees (i.e., trees in which a node labeled by a given symbol may have any number of children). The resulting notions of recognizability and definability are not fully equivalent but they are closely related. More precisely, every recognizable series of unranked trees over a semiring \(S\) is definable in the weighted MSO-logic, and every series definable in a syntactically restricted form of this logic is recognizable. If \(S\) is commutative, then every recognizable series is definable by an existential formula of the restricted logic. It is also shown that, for series of ranked trees, recognizability is equivalent to definability in an appropriate variant of the restricted logic. Finally, the authors demonstrate by some examples how quantitative queries in XML-type databases can be formulated in their weighted MSO-logic.