
Evènement pour le groupe Modélisation et Verification
Date  20111013 11:3012:30 
Titre  Weighted 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 treewalking 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. 
Lieu  L'Amphi 
Orateur  Benjamin Monmege 
Email  Benjamin.Monmege@lsv.enscachan.fr 
Url  LSV, ENS Cachan 
Aucun document lié à cet événement. RetourRetour à l'index
 