Graphen mit entscheidbaren Logiken (GELO)

• Antragsteller: Professor Dr. Markus Lohrey
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2006 bis 2015
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 31332468

• Erstellungsjahr: 2015

Zusammenfassung der Projektergebnisse

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.