Auflistung nach Autor:in "Elberfeld, Michael"
1 - 1 von 1
Treffer pro Seite
Sortieroptionen
- TextdokumentPlatz- und Schaltkreiskomplexität von MSO-beschreibbaren Problemen auf baumartig zerlegbaren Strukturen(Ausgezeichnete Informatikdissertationen 2012, 2013) Elberfeld, MichaelDieser 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.