Algorithmische Theorie der Baumautomaten

• Antragsteller: Privatdozent Dr. Christof Löding
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2005 bis 2011
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5445837

• Erstellungsjahr: 2015

Zusammenfassung der Projektergebnisse

In dem Projekt wurden neue Ergebnisse zu aktuellen Themen der theoretischen Informatik im Bereich der Automatentheorie erzielt. Einerseits wurden Automaten und Logiken untersucht, wie sie in den letzten Jahren verstärkt im Rahmen der formalen Analyse von XML-Spezifikationen betrachtet wurden. Die Resultate aus unserem Projekt tragen zur Klärung der algorithmischen Eigenschaften dieser Formalismen sowie deren Einordnung in das Gesamtbild bei, das sich aus einer Fülle von verwendeten Modellen ergibt. Ein weiterer Schwerpunkt des Projektes, der sich im Laufe der zweiten Förderperiode etabliert hat, war die Analyse von Automatenmodellen zur Modellierung von Beschränkheitsfragen. Solche Modelle finden z.B. Anwendung in der Modellierung von Systemen mit Ressourcen, für die man algorithmische Fragen unter einer Beschränkung des Ressourcenverbrauchs lösen möchte. In dem Projekt ist es in Zusammenarbeit mit T. Colcombet gelungen, durch neue Konstruktionen und Algorithmen die relativ neue Theorie dieser Automaten und deren Verbindung zur Logik voranzutreiben.

Projektbezogene Publikationen (Auswahl)

• 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
  Christof Löding and Alex Spelten
  
• Unranked tree automata with sibling equalities and disequalities. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, volume 4596 of Lecture Notes in Computer Science, pages 875-887. Springer, 2007
  Wong Karianto and Christof Löding
  
• 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
  Frank G. Radmacher
  
• 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
  T. Colcombet and C. Löding
  
• Lernverfahren för Automaten öber linearisierten XML-Dokumenten. In Informatik Spektrum 32(3), pages 255-259. Springer, 2009
  D. Neider
  
• On nondeterministic unranked tree automata with sibling constraints. In Ravi Kannan and K. Narayan Kumar, editors, 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, Dagstuhl, Germany, 2009. Schloss Dagstuhl - Leibniz-Zentrum för Informatik
  Christof Löding and Karianto Wong
  
• Basics on tree automata. In Deepak D’Souza and Priti Shankar, editors, Modern Applications of Automata Theory. World Scientific, 2012
  C. Löding
  
• Finite Automata on Unranked Trees: Extensions by Arithmetical and Equality Constraints. Dissertation, RWTH Aachen, June 2010
  Karianto Wong
  
• Learning Visibly One-Counter Automata in Polynomial Time. Technical Report AIB-2010-02, RWTH Aachen, January 2010
  Daniel Neider and Christof Löding
  
• Regular cost functions over finite trees. In Twenty-Fifth Annual IEEE Symposium on Logic in Computer Science, LICS 2010, pages 70-79. IEEE Computer Society, 2010
  T. Colcombet and C. Löding