Konstruktionen und Modelltheorie für Hypergraphen kontrollierter Azyklizität

点击翻译按钮获取中文摘要

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.