We research the relationship between two classes of weighted tree languages.
•
We give a construction from one automaton model to the other preserving the language.
•
An analogous result is shown for the corresponding weighted tree logics.
•
A direct transformation between the logics avoids nonelementary blow-up.
Abstract
Weighted tree languages over semirings lack the expressive power to model computations like taking the average or the discounting of weights in a straightforward manner. This limitation was overcome by weighted tree automata and logics using (a) tree valuation monoids and (b) multioperator monoids. We compare the expressive power of these two solutions and show that a weighted tree language recognizable (resp. definable) over a tree valuation monoid is also recognizable (resp. definable) using a multioperator monoid. For this, we provide direct, semantic-preserving transformations between the automata models and between the respective logics.