Evènement pour le groupe Modélisation et Verification

Date 2011-10-13  11:30-12:30
TitreWeighted Expressions and Pebble Automata over Nested Words 
RésuméWe introduce a calculus over nested words (or equivalently, trees) to express quantitative properties of XML documents or recursive programs. Our weighted expressions borrow purely logical constructs from XPath, but they also involve rational arithmetic expressions. The latter allow us to perform computations in an arbitrary (commutative) semiring. For instance, one can count how often a given entry occurs in an XML document, or compute the memory consumption of a program execution. We characterize a fragment of weighted expressions in terms of a new class of weighted automata. In the spirit of tree-walking automata, our device traverses a nested word along its edges and may place pebbles during a traversal. After proving this expressiveness result, we give a list of interesting decision or computation problems, with some hints on their resolution, and a set of possible applications of these problems, depending of the chosen semiring. 
OrateurBenjamin Monmege 
UrlLSV, ENS Cachan 

Aucun document lié à cet événement.

Retour à l'index