Automata and Logic on Trees
This is the homepage of the course "Automata and Logic on Trees"
given at the 19th European Summer School on Logic, Language and
Information in Dublin, Ireland from 6-11 august 2007 by Wim Martens and Stijn Vansummeren.
Abstract
Regular languages are a fundamental concept in Computer Science.
However, as undergraduate courses usually do not go beyond regular
languages over strings, the elegant generalisation to regular tree
languages is less known. Nevertheless, regular tree languages have
become highly relevant for XML-related research. Indeed, finite
automata for tree languages serve as a formal model of XML schema
languages such as XML Schema, and their computational properties form
the basis of many static analysis algorithms. The logical counterpart
of finite automata over trees is Monadic Second Order logic (MSO). This
connection allows to infer, e.g., closure properties and decidability
of many decision problems. We provide a rigorous introduction
to tree automata and their logical counterpart. In particular, we treat
ranked tree automata, constructions on automata, closure properties,
complexity of decision problems, MSO on trees, its correspondence to
tree automata, unranked tree automata, and their application to XML.
Slides of Lectures
Bibliography
- Automata, Logic, and XML. Frank Neven, Lecture Notes in Computer Science vol 2471, pages 2–26.
- Automata Theory for XML Researchers. Frank Neven, Sigmod Record 31(3), pages 39-46
- Tree Automata Techniques and Applications.
- Languages, automata, and logic. Wolfgang Thomas, Handbook of formal languages, vol. 3: beyond words, Springer, 1997
- Minimization of XML Schemas and Tree Automata for Unranked Trees. Wim Martens and Joachim Niehren. Journal of Computer and System Sciences, 73(4), pp. 550-583, 2007.
|