Approximations by OBDDs and the Variable Ordering Problem

Created by W.Langdon from gp-bibliography.bib Revision:1.7642

@TechReport{Krause:1999:OBDD,

• author = "Matthias Krause and Petr Savicky and Ingo Wegener",
• title = "Approximations by {OBDDs} and the Variable Ordering Problem",
• institution = "Dept. of Computer Science/XI, Universitaet Dortmund",
• year = "1999",
• number = "CI-58/99",
• address = "Germany",
• month = jan,
• keywords = "genetic algorithms, genetic programming",
• ISSN = "1433-3325",
• URL = "https://eldorado.tu-dortmund.de/bitstream/2003/5367/1/ci58.pdf",
• URL = "https://eldorado.tu-dortmund.de/handle/2003/5367",
• URL = "http://hdl.handle.net/2003/5367",
• DOI = "doi:10.17877/DE290R-15157",
• size = "13 pages",
• 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 pi0 , all functions which approximate them on considerably more than half of the inputs, need exponential pi0-OBDD size. These results have implications for the use of OBDDs in genetic programming.",
• notes = "In English. See also \cite{KRAUSE2005160}",

}

Genetic Programming entries for Matthias Krause Petr Savicky Ingo Wegener

Citations