Platz- und Schaltkreiskomplexität von MSO-beschreibbaren Problemen auf baumartig zerlegbaren Strukturen

dc.contributor.author	Elberfeld, Michael
dc.contributor.editor	Hölldobler, Steffen
dc.date.accessioned	2020-08-21T08:45:55Z
dc.date.available	2020-08-21T08:45:55Z
dc.date.issued	2013
dc.description.abstract	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.	de
dc.identifier.isbn	978-3-88579-417-2
dc.identifier.pissn	1617-5468
dc.identifier.uri	https://dl.gi.de/handle/20.500.12116/33722
dc.language.iso	de
dc.publisher	Gesellschaft für Informatik
dc.relation.ispartof	Ausgezeichnete Informatikdissertationen 2012
dc.relation.ispartofseries	Lecture Notes in Informatics (LNI) - Dissertations, Volume D-13
dc.title	Platz- und Schaltkreiskomplexität von MSO-beschreibbaren Problemen auf baumartig zerlegbaren Strukturen	de
gi.citation.endPage	80
gi.citation.publisherPlace	Bonn
gi.citation.startPage	71

Dateien

1 - 1 von 1