Automata and logics on structures with data

Ranko Lazic
University of Warwick
Friday, 8 May, 2009 (All day)

Even without continuous phenomena, words and trees over finite alphabets are sometimes insufficiently detailed models. A prominent example is processing semistructured data, which may involve attribute values from infinite domains. With such a motivation, several formalisms for reasoning about words and trees with infinitary data have recently been studied, using a variety of techniques. The emerging landscape is interesting, but careful navigation is required for avoiding undecidability and very high complexity.