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
XPath: expressive power and static analysis
- Date
- Tuesday, July 07 2009 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Balder ten Cate (INRIA, ENS Cachan)
XPath is a language for navigating in XML documents. It is part of the W3C standard XML querying and processing languages XQuery and XSLT. From the perspective of logic, XPath can be understood as a variant of temporal logics on finite trees. In this talk, I will discuss two aspects of XPath 1.0 and 2.0 (as well as of some other variants of XPath proposed in the literature):
- Expressivity and succinctness: Which paths through XML documents can be described in XPath, and how succinctly? One way to answer this is by comparing XPath to more well established and understood languages such as first-order logic.
- Static analysis: What is the complexity of testing whether two XPath expressions are equivalent (always give the same answer)? Can we find a complete set of equivalence-preserving rewrite rules (i.e., so that every two equivalent expressions can be rewritten to each other using these rules)?