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], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
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.
Type de document :
[Research Report] LSV-11-08, 2011
Liste complète des métadonnées

Contributeur : Stefan Haar <>
Soumis le : mardi 22 janvier 2013 - 17:38:39
Dernière modification le : jeudi 24 mai 2018 - 09:34:04


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



Consultations de la notice