---

Automata for XML

Validating XML DTDs (Document Type Definitions), navigating and query processing become difficult when we work not only with tags but also data values. Abstractly this involves reasoning about languages over infinite (data) alphabets.

Inspired by XML applications, recent research has started looking for automata theoretic studies of data languages: these are sets of words over an alphabet Sigma X D, where Sigma is a finite alphabet (as usual), but D is an infinite set of data values, over which equality is decidable. An example instance is the XPath query: find all books by Thomas with the same editor.

While such automata are typically too expressive (undecidable emptiness problem, for instance), there have been some encouraging results recently. In this lecture, we survey automata over infinite alphabets designed for this purpose