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