Algorithmic Theory of Tree Automata

Project Description

Contents

The theory of (finite) tree automata is a foundation of the description and solution of many algorithmic problems in such diverse areas as term rewriting, type-checking, model-checking, and data base query languages. In the latter areas of application it emerged that the classical model of a tree automaton has to be modified in order to enable the desired tasks. Thus, in the context of semi-structured data (XML), trees of unrestricted branching factor ("unranked trees") have to be considered, as well as (for the modelling of query operations) path oriented automata models ("tree walking automata"), which navigate through trees along the tree edges.

At present, a manageable and algorithmically useable theroretical foundation of these models of tree automata exists only in its beginnings. The first aim of our scheme is to develop algorithmic solutions for the synthesis and analysis of these automata in a more general framework than currently existing, as well as to accomplish a clearer interconnectedness with logical formalisms.

A second aim consists of developing new applications in the algorithmic verification over infinite state spaces (with case studies on the formal analysis of crypto protocols). Hereby we employ the method of describing (as well as efficiently computing) sets of reachable states by tree automata over unranked trees.

Publications

2009

[LW09] Christof Löding and Karianto Wong. On nondeterministic unranked tree automata with sibling constraints. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009), volume 4 of Leibniz International Proceedings in Informatics (LIPIcs), pages 311-322. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2009.

2008

[Rad08a] Frank G. Radmacher. An automata theoretic approach to rational tree relations. In Proceedings of the 34th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2008, volume 4910 of Lecture Notes in Computer Science, pages 424-435. Springer, 2008.
[CL08a] T. Colcombet and C. Löding. The nesting-depth of disjunctive mu-calculus for tree languages and the limitedness problem. In Proceedings of the 17th EACSL Annual Conference on Computer Science Logic CSL 2008, volume 5213 of Lecture Notes in Computer Science. Springer, 2008.

2007

[KL07] Wong Karianto, Christof Löding. Unranked Tree Automata with Sibling Equalities and Disequalities. Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP 2007. Lecture Notes in Computer Science 4596, pages 875–887. Springer, 2006.
[LS07] Christof Löding, Alex Spelten. Transition Graphs of Rewriting Systems over Unranked Trees. In Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007., volume 4708 of Lecture Notes in Computer Science, pages 67-77. Springer 2007.
A preliminary version is accepted at the international conference AutoMathA 2007, Automata: from Mathematics to Applications, Palermo, Italy, 2007.
[Rad07] Frank Radmacher. Automatendefinierbare Relationen über XML-Bäumen. Diploma thesis, RWTH Aachen, March 2007.

2006

[BLS06] Vince Bárány, Christof Löding, and Olivier Serre. Regularity problems for visibly pushdown languages. Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science, STACS 2006. Lecture Notes in Computer Science 3884, pages 420-431. Springer, 2006.
[Gro06] Benoît Groz. Counting over Unranked Trees. Internship Report, RWTH Aachen, August 2006.
[KKT06] Wong Karianto, Aloys Krieg, Wolfgang Thomas. On Intersection Problems for Polynomially Generated Sets. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, Part II. Lecture Notes in Computer Science 4052, pages 516–527. Springer, 2006.
[KL06] Wong Karianto, Christof Löding. Unranked Tree Automata with Sibling Equalities and Disequalities. Technical Report AIB-2006-13, RWTH Aachen, October 2006.
[Spe06] Alex Spelten. Rewriting Systems over Unranked Trees. Diploma thesis, RWTH Aachen, September 2006.

2005

[CLT05] Julien Cristau, Christof Löding, Wolfgang Thomas. Deterministic Automata on Unranked Trees. Proceedings of the 15th International Symposium on Fundamentals of Computation Theory, FCT 2005. Lecture Notes in Computer Science 3623, pages 68-79. Springer, 2005.
[Hin05] Gregor Hink. Pfadorientierte Automaten und Logiken über Bäumen. Diploma thesis, RWTH Aachen, August 2005.

Activities

Diploma Theses

Completed Diploma Theses