A link between multioperator and tree valuation automata and logics

作者：Teichmann Markus^*; Osterholzer Johannes

来源：Theoretical Computer Science, 2015, 594: 106-119.

DOI：10.1016/j.tcs.2015.04.033

• Weighted tree automaton
• Weighted logic
• Multioperator monoid
• Tree valuation monoid

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.

• 出版日期2015-8-23