Automatentheoretische Verifikationsprobleme mit Ressourcenschranken

• Applicant: Privatdozent Dr. Christof Löding
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 213443580

• Final Report Year: 2015

Final Report Abstract

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.

Publications

• 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
  (See online at https://doi.org/10.1007/978-3-662-44522-8_33)
• 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
  (See online at https://doi.org/10.1007/978-3-642-54830-7_13)