Automatentheoretische Verifikationsprobleme mit Ressourcenschranken

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

• Erstellungsjahr: 2015

Zusammenfassung der Projektergebnisse

In dem Projekt wurden neue Ergebnisse zu aktuellen Themen der theoretischen Informatik im Bereich der Automatentheorie erzielt. Insbesondere wurde eine algorithmische Theorie unendlicher Systeme mit Ressourcenverbrauch entwickelt. Es handelt sich dabei um Grundlagenforschung, die erzielten Ergebnisse können jedoch als Basis für weitere Entwicklungen zur automatischen Verifikation von Systemen mit Ressourcenverbrauch dienen. Desweiteren wurden in den letzten Jahren unterschiedliche quantitativen Logiken zur Formalisierung von Beschränkheitseigenschaften definiert. In dem Projekt ist es gelungen, Verbindungen zwischen diesen Logiken herzustellen und somit die damit verbundene Theorie voranzutreiben.

Projektbezogene Publikationen (Auswahl)

• Deciding the weak definability of Büchi definable tree languages. In Proceedings of the 22nd Annual Conference of the European Association for Computer Science Logic, CSL 2013, Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013
  Thomas Colcombet, Denis Kuperberg, Christof Löding, and Michael Vanden Boom
  
• Modeling and Verification of Infinite Systems with Resources. In Logical Methods in Computer Science 9(4), 2013
  Martin Lang and Christof Löding
  
• Definability and Transformations for Cost Logics and Automatic Structures. In Proceedings of Mathematical Foundations of Computer Science 2014. Lecture Notes in Computer Science series, volume 8634, Springer Berlin Heidelberg, 2014, pages 390-401
  Martin Lang, Christof Löding and Amaldev Manuel
  
• Resource Reachability Games on Pushdown Graphs. In Proceedings of Foundations of Software Science and Computation Structures, FoSSaCS 2014. Lecture Notes in Computer Science series, volume 8412, Springer Berlin Heidelberg, pages 195-209. 2014
  Martin Lang