LSV Seminar

The LSV seminar takes place on Tuesday at 11:00 AM. The usual location is the conference room at Pavillon des Jardins (venue). If you wish to be informed by e-mail about upcoming seminars, please contact Stéphane Le Roux and Matthias Fuegger.

The seminar is open to public and does not require any form of registration.

Past Seminars

Tree Pattern Rewriting Systems

Tuesday, October 28 2008 at 11:00AM
Salle de Conférence (Pavillon des Jardins)
Olivier Serre (CNRS, LIAFA, Paris)

Classical verification often uses abstraction when dealing with data. On the other hand, dynamic XML-based applications have become pervasive, for instance with the ever growing importance of web services. We define here Tree Pattern Rewriting Systems (TPRS) as an abstract model of dynamic XML-based documents. TPRS systems generate infinite transition systems, where states are unranked and unordered trees (hence possibly modeling XML documents). The guarded transition rules are described by means of tree patterns. Our main result is that given a TPRS system (T,R), a tree pattern P and some integer k such that any reachable document from T has depth at most k, it is decidable (albeit of non elementary complexity) whether some tree satisfying P is reachable from T. This is joint work with B. Genest, A. Muscholl, and M. Zeitoun.

About LSV