Automata and logics for data values

An XML document is commonly modeled as a tree, with nodes labeled by a finite alphabet. Properties of such documents can be expressed using finite tree automata, which are well understood and admit efficient algorithms. However, the finite alphabet representation does not capture some aspects of a document, such as references or keys. It is not clear how to add these features, while still retaining the benefits of finite automata. I will talk about recent work in this direction.