Approximations by OBDDs and the variable ordering problem

Krause, Matthias ; Savický, Petr ; Wegener, Ingo

Additional URL:
Document Type: Working paper
Year of publication: 1999
The title of a journal, publication series: Electronic Colloquium on Computational Complexity : ECCC
Volume: TR99-011
Place of publication: Trier
Publishing house: Universität Trier
ISSN: 1433-8092
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause)
Subject: 004 Computer science, internet
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.
Additional information: Online-Ressource

Dieser Eintrag ist Teil der Universitätsbibliographie.

Metadata export


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item