Zur Ausdrucksstärke monadischer Logik zweiter Stufe

• Antragsteller: Professor Dr. Achim Blumensath
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 191668914

Die monadische Logik zweiter Stufe ist eine etablierte Standardlogik in der theoretischen Informatik, deren Anwendungen vor allem in Verifikation, der Theorie formaler Sprachen und der Graphentheorie liegen. Dabei hat die Ausdrucksstärke dieser Logik und ihrer Fragmente von Anfang an eine bedeutende Rolle gespielt. In jüngster Zeit haben sich auf diesem Gebiet einige vielversprechende Ansätze ergeben, die im Rahmen des Projekts verfolgt werden sollen.(a) Es soll eine algebraische Sprachtheorie für unendliche Bäume entwickelt werden. Hieraus sollen Entscheidungsverfahren für Fragmente dermonadischen Logik zweiter Stufe gewonnen werden.(b) Es sollen entscheidbare Erweiterungen dermonadischen Logik zweiter Stufe gefunden werden. Gedacht ist hier insbesondere an Erweiterungen um Beschränktheitsaussagen.(c) Die Ausdrucksstärke von Transduktionen auf unendlichen Strukturen soll geklärt werden.

• DFG-Verfahren: Sachbeihilfen