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.
One difficulty when we want to specify and manipulate XML documents is to deal with data. Here we represent an XML document as a tree labelled by an infinite alphabet to represent data values. We consider Boolean combinations of data tree patterns as a specification and query language for XML documents. Data tree patterns are tree patterns plus variable (in)equalities which express joins between data values. We consider the decidability and complexity of two problems. The first one is the model checking problem. We show that it is DP-complete in general and already NP-complete when we consider a single pattern. The second one is the satisfiability problem in the presence of a DTD. We show that it is in general undecidable and we identify several decidable fragments.