Graphen mit entscheidbaren Logiken (GELO)

• Applicant: Professor Dr. Markus Lohrey
• Subject Area: Theoretical Computer Science
• Term: from 2006 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 31332468

• Final Report Year: 2015

Final Report Abstract

Das GELO-Projekt kann abschließend als sehr erfolgreich bewertet werden. Für mehrer wichtige Klassen von unendlich präsentierten Graphen konnte die Komplexität des Model-Checking Problems für diverse Logiken (Logik 1. Stufe, EF, CTL) geklärt werden. Als zweiter bedeutender Beitrag wurde unser Bild zu Isomorphieproblemen für unendliche endlich präsentierte Strukturen maßgeblich präzisiert. Die Arbeit an dem GELO-Projekt wird sich auch nachhaltig auf die zukünftige Arbeit zu Logiken über unendlichen Graphen auswirken. Die durch das GELO-Projekt erworbene Expertise ist auch in die Arbeit des Projektleiters im Rahmen des von der DFG geförderten Graduiertenkollegs 1763 (QuantLA) gewinnbringend eingeflossen.