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

Visit website for this news | Export event in iCalendar format

 Balder ten Cate
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)?

Based on joint works with Maarten Marx, with Carsten Lutz, and with Luc Segoufin.


About LSV

Agenda

Export agenda in iCalendar format | Past seminars

Tue, Jan 29
Tue, Feb 5
Tue, Feb 19

Past seminars