Textdokument
Platz- und Schaltkreiskomplexität von MSO-beschreibbaren Problemen auf baumartig zerlegbaren Strukturen
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Dateien
Zusatzinformation
Datum
2013
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik
Zusammenfassung
Dieser 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.