|
Approximations by OBDDs and the variable ordering problem
Krause, Matthias
;
Savický, Petr
;
Wegener, Ingo
|
URL:
|
https://eccc.weizmann.ac.il/report/1999/011/
|
|
Weitere URL:
|
https://www.semanticscholar.org/paper/Approximatio...
|
|
Dokumenttyp:
|
Arbeitspapier
|
|
Erscheinungsjahr:
|
1999
|
|
Titel einer Zeitschrift oder einer Reihe:
|
Electronic Colloquium on Computational Complexity : ECCC
|
|
Band/Volume:
|
TR99-011
|
|
Ort der Veröffentlichung:
|
Trier
|
|
Verlag:
|
Universität Trier
|
|
ISSN:
|
1433-8092
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Theoretische Informatik (Krause 1996-)
|
|
Fachgebiet:
|
004 Informatik
|
|
Abstract:
|
Ordered binary decision diagrams (OBDDs) and their variants are motivated by the need to represent Boolean functions in applications. Research concerning these applications leads
also to problems and results interesting from theoretical point of view. In this paper, methods from communication complexity and information theory are combined to prove that the direct storage access function and the inner product function have the following property. They have linear \pi-OBDD size for some variable ordering \pi and, for most variable orderings \pi', all functions which approximate them on considerably more than half of the inputs, need exponential \pi'-OBDD size. These results have implications for the use of OBDDs in experiments with genetic programming.
|
|
Zusätzliche Informationen:
|
Online-Ressource
|
 | Dieser Eintrag ist Teil der Universitätsbibliographie. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
