Universal Logic

We present logical methods for querying semistructured data, in particular XML documents. Models for such documents are finite node labeled sibling ordered trees. Several logics are useful to query such data, and in fact the logical core of the W3C standard XPath is nothing but a modal logic. We discuss temporal logic, PDL and Kozen's Kleene algebras with tests as formalisms for reasoning and querying these kind of trees. The primary focus will be on techniques for obtaining expressivity and complexity results. No background on XML is needed. Some logical background is required, that is familiarity with first order logic and preferably the basics of modal logic.

This course is intended for people who like to see logics in action, and who are interested in designing logical systems for a particular problem.



	Logics of semistructured data Maarten Marx Informatics Institute Universiteit van Amsterdam
	We present logical methods for querying semistructured data, in particular XML documents. Models for such documents are finite node labeled sibling ordered trees. Several logics are useful to query such data, and in fact the logical core of the W3C standard XPath is nothing but a modal logic. We discuss temporal logic, PDL and Kozen's Kleene algebras with tests as formalisms for reasoning and querying these kind of trees. The primary focus will be on techniques for obtaining expressivity and complexity results. No background on XML is needed. Some logical background is required, that is familiarity with first order logic and preferably the basics of modal logic. This course is intended for people who like to see logics in action, and who are interested in designing logical systems for a particular problem. Lecture notes - slides