Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 (Research report)
Complete list of metadata
Contributor : Stefan Haar Connect in order to contact the contributor
Submitted on : Tuesday, January 22, 2013 - 5:38:39 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:38 AM


  • HAL Id : hal-00779951, version 1


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



Record views