Elsevier

Theoretical Computer Science

Volume 594, 23 August 2015, Pages 106-119
Theoretical Computer Science

A link between multioperator and tree valuation automata and logics

https://doi.org/10.1016/j.tcs.2015.04.033Get rights and content
Under an Elsevier user license
open archive

Highlights

  • 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.

Keywords

Weighted tree automaton
Weighted logic
Multioperator monoid
Tree valuation monoid

Cited by (0)