Logo des Repositoriums
 
Textdokument

Multiplikation in eingeschränkten Branchingprogrammmodellen

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Zusatzinformation

Datum

2004

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik

Zusammenfassung

und Ausblick Wir können nicht erwarten, auf die eingangs gestellte Frage nach der Komplexität der Multiplikation in naher Zukunft für irgendein allgemeines Rechenmodell wie Schaltkreise oder Branchingprogramme eine vollständige Antwort zu finden. Wir können aber versuchen, nach und nach zu umfassenderen Erkenntnissen über die Multiplikation zu gelangen und neue Techniken zum Nachweis oberer und unterer Schranken zu entwickeln, um auf diese Weise die Komplexität der Multiplikation besser einzugrenzen. Die Ergebnisse der Dissertation stellen einen weiteren Schritt in diese Richtung dar. Dass dies nicht der letzte war, zeichnet sich schon an einer Reihe weiterführender Erkenntnisse über die Branchingprogrammkomplexität der Multiplikation ab. So konnten z. B. in [BWW02] und [BW] exponentielle untere Schranken in weiteren eingeschränkten nichtdeterministischen FBDD-Modellen nachgewiesen werden und kürzlich zeigten Sauerhoff und Woelfel exponentielle untere Schranken für nichtdeterministische Branchingprogramme, bei denen jede Variable auf jedem graphtheoretischen Pfad konstant oft vorkommen darf [SW03]. Literatur [Br85] Bryant, R. E.: Symbolic manipulation of boolean functions using a graphical representation. Proceedings of the 22nd ACM/IEEE Design Automation Conference (DAC). S. 688-694. 1985. [Br86] Bryant, R. E.: Graph-ba

Beschreibung

Wölfel, Philipp (2004): Multiplikation in eingeschränkten Branchingprogrammmodellen. Ausgezeichnete Informatikdissertationen 2003. Bonn: Gesellschaft für Informatik. PISSN: 1617-5468. ISBN: 978-3-88579-408-X. pp. 199-208

Schlagwörter

Zitierform

DOI

Tags