Elberfeld, MichaelHölldobler, Steffen2020-08-212020-08-212013978-3-88579-417-2https://dl.gi.de/handle/20.500.12116/33722Dieser Beitrag ist eine deutschsprachige Kurzfassung der Dissertation von Michael Elberfeld [Elb12]. Die Dissertation entwickelt und bearbeitet Fragestellungen aus den Bereichen der Theoretischen Informatik und Mathematischen Logik. Sie untersucht die Platz-, Schaltkreis- und Beschreibungskomplexität von Problemen, die sich durch Formeln in monadischer Logik zweiter Stufe beschreiben lassen und deren Eingaben eine beschränkte Baumweite oder -tiefe besitzen. Die gewonnenen Resultate werden angewendet, um die Komplexität konkreter Entscheidungs-, Zähl- und Optimierungsprobleme aus verschiedenen Anwendungsgebieten zu klassifizieren.de1617-5468