Automata and logics for data values

Speaker(s)

Mikolaj Bojanczyk

Affiliation

Uniwersytet Warszawski

Date

Nov. 7, 2007, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---