Show simple item record

dc.contributor.authorDolzmann, Andreas
dc.contributor.editorWagner, Dorothea
dc.date.accessioned2017-09-22T20:40:44Z
dc.date.available2017-09-22T20:40:44Z
dc.date.issued2003
dc.identifier.isbn3-88579-405-5
dc.identifier.issn1617-5468
dc.identifier.urihttp://dl.gi.de/handle/20.500.12116/4425
dc.description.abstractEines der bedeutendsten Verfahren zur reellen Quantorenelimination ist die Quantorenelimination mittels virtueller Substitution, die von Weispfenning 1988 eingeführt wurde. In der vorliegenden Arbeit werden zahlreiche algorithmische Strategien zur Optimierung dieses Verfahrens präsentiert. Optimierungsziele der Arbeit waren dabei die tatsächliche Laufzeit der Implementierung des Algorithmus sowie die Größe der Ausgabeformel. Zur Optimierung werden dabei die Simplifikation von Formeln erster Stufe, die Reduktion der Größe der Eliminationsmenge sowie das Condensing, ein Ersatz für die virtuelle Substitution, untersucht. Lokale Quantorenelimination berechnet Formeln, die nur in der Nähe eines gegebenen Punktes äquivalent zur Eingabeformel ist. Diese Einschränkung erlaubt es, das Verfahren weiter zu verbessern. Als Anwendung des Eliminationsverfahren diskutieren wir abschließend, wie man eine große Klasse von Schedulingproblemen mittels reeller Quantorenelimination lösen kann. In diesem Fall benutzen wir die spezielle Struktur der Eingabeformel und zusätzliche Informationen über das Schedulingproblem, um die Quantorenelimination mittels virtueller Substitution problemspezifisch zu optimieren.
dc.language.isode
dc.publisherGesellschaft für Informatik
dc.relation.ispartofAusgezeichnete Informatikdissertationen 2000
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Dissertations, Volume D-1
dc.titleAlgorithmische Strategien für anwendbare reelle Quantoreneliminationde
dc.pubPlaceBonn
mci.reference.pages43-52


Files in this item

Thumbnail

Show simple item record