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