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

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.

Domaines: Autre [cs.OH]

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