Skip to Main content Skip to Navigation
Reports

Weighted Expressions and DFS Tree Automata

Benedikt Bollig 1 Paul Gastin 1 Benjamin Monmege 1 Marc Zeitoun 1
1 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], Inria Saclay - Ile de France
Abstract : We introduce weighted expressions, a calculus to express quantitative properties over unranked trees. They involve products and sums from a semiring as well as classical boolean formulas. We show that weighted expressions are expressively equivalent to a new class of weighted tree-walking automata. This new automata model is equipped with pebbles, and follows a depth-first-search policy in the tree.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/hal-00779951
Contributor : Stefan Haar <>
Submitted on : Tuesday, January 22, 2013 - 5:38:39 PM
Last modification on : Monday, February 15, 2021 - 10:49:08 AM

Identifiers

  • HAL Id : hal-00779951, version 1

Collections

Citation

Benedikt Bollig, Paul Gastin, Benjamin Monmege, Marc Zeitoun. Weighted Expressions and DFS Tree Automata. [Research Report] LSV-11-08, 2011. ⟨hal-00779951⟩

Share

Metrics

Record views

311