Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Weighted Expressions and Pebble Automata over Nested Words
du 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. 
LieuL'Amphi 
OrateurBenjamin Monmege 
EmailBenjamin.Monmege@lsv.ens-cachan.fr 
UrlLSV, ENS Cachan 



Aucun document lié à cet événement.

Retour
Retour à l'index