Anwendungen monadischer Logik zweiter Stufe auf Probleme beschränkter Baumweite und deren Platzkomplexität

Die parametrisierte Komplexitätstheorie befasst sich mit der komplexitätstheoretischen Untersuchung von Problemen unter besonderer Beachtung ihrer inhärenten Parameter. Historisch bedingt liegt der Fokus dabei auf der Untersuchung der Zeitkomplexitäten von Problemen. In dieser Arbeit wird ein Framework eingeführt, welches die parametrisierte Komplexitätstheorie um Komplexitätsklassen und einen passenden Reduktionsbegriff erweitert, die erste systematische Untersuchungen bezüglich der Platzkomplexitäten von Problemen ermöglichen. Weiter wird eine Auswahl von klassischen Problemen unter Verwendung dieses Frameworks analysiert. Dies beinhaltet verschiedene Varianten, vor allem Zählvarianten, von Zahlenproblemen, dem Erfüllbarkeitsproblem für aussagenlogische Formeln sowie Graphen- und Mengenproblemen, die mittels der Logspace-Versionen der Sätze von Bodlaender und Courcelle bezüglich ihrer Platzkomplexität klassifiziert werden. Abschließend gibt diese Arbeit einen Ausblick auf weiterführende Entwicklungen der parametrisierten Platzkomplexität.