# 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

### Data Tree Patterns

- Date
- Tuesday, April 08 2008 at 11:00AM
- Place
- Salle de Conférence (Pavillon des Jardins)
- Speaker
- Claire David (LIAFA)

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.