Charla: Models of computation for static analysis in web databases (en inglés)

Tony Tan, School of Informatics University of Edinburgh
5 Mayo, 2011 - 16:00
Sala Auditorio cuarto piso


The web has brought fundamentally new challenges to data management. The key features that distinguish web data from traditional database applications are its structure: usually described by mark-up languages, such as XML.

The simplest abstraction of XML documents is ordered unranked finite trees whose nodes are labeled by letters from a finite alphabet. This abstraction works well for reasoning about structural properties, but real XML documents carry data, which cannot be captured by a finite alphabet. Thus, there has been a consistent interest in data trees, i.e., trees in which nodes carry both a label from a finite alphabet and a data value from an infinite domain. It seems natural to add at least the equality on data values to a logic over data trees. But while for finitely-labeled trees many logical formalisms -such as monadic second-order logic- are decidable; adding data-equality makes even first-order logic undecidable. This explains why the search for decidable reasoning formalisms over data trees has been a common theme in XML research.

In this talk I will give a brief survey on results and techniques that have been developed in the research of data trees and data words. Some of the results have surprisingly deep connections with other well known models of computation such as vector addiction systems and automata with Presburger constraints.

Comunicaciones DCC