Konstruktionen und Modelltheorie für Hypergraphen kontrollierter Azyklizität

• Applicant: Professor Dr. Martin Otto
• Subject Area: Theoretical Computer Science
• Term: from 2012 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 210896119

Azyklizitätskriterien spielen in vielen Bereichen der algorithmischen Modelltheorie und der Logik in der Informatik eine Rolle. Azyklizität erweist sich als nützlich für die Komplexität algorithmischer Probleme wie für die modelltheoretische Analyse. Oft können ideale Azyklizitätsbedingungen durch Abwicklungs- und Überlagerungskonstruktionen erreicht werden; typische Konstruktionen (wie Baumabwicklungen) stehen aber i.d.R. nicht zur Verfügung wenn man sich aufgrund der Problemstellung auf endliche Strukturen beschränken muss. Hier werden qualitativ und quantitativ eingeschränkte Approximationen wichtig und es geht darum(i) geeignete approximative Azyklizitätsbegriffe zu isolieren, die entsprechende endliche Überlagerungs- oder Abwicklungskonstruktionen erlauben, und(ii) Methoden zu gewinnen, die gute algorithmische oder logische Eigenschaften bei solchermaßen kontrollierter Azyklizität verfügbar machen.Neue Konstruktionsmethoden, neue Techniken zur Analyse und neue Anwendungsbereiche sollen in einem weiteren Kontext - ausgehend von den entscheidenden Durchbrüchen in [4, 35] - systematisch erforscht und entwickelt werden.

• DFG Programme: Research Grants