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.




Metadaten-Export


Zitation


+ Suche Autoren in

+ Aufruf-Statistik

Aufrufe im letzten Jahr

Detaillierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen