Approximability and Non-Approximability by Binary Decision Diagrams (Extended Abstract)

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

@Misc{oai:CiteSeerX.psu:10.1.1.36.6062,

• author = "Beate Bollig and Martin Sauerhoff and Ingo Wegener",
• title = "Approximability and Non-Approximability by Binary Decision Diagrams (Extended Abstract)",
• year = "1995",
• annote = "The Pennsylvania State University CiteSeerX Archives",
• bibsource = "OAI-PMH server at citeseerx.ist.psu.edu",
• language = "en",
• oai = "oai:CiteSeerX.psu:10.1.1.36.6062",
• rights = "Metadata may be used without restrictions as long as the oai identifier remains attached to it.",
• keywords = "genetic algorithms, genetic programming, subject classification, computational and structural complexity",
• URL = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.6062",
• URL = "http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.6062.pdf",
• broken = "http://ls2-www.cs.uni-dortmund.de/~wegener/papers/Paper95a.ps",
• size = "22 pages",
• abstract = "The usual applications of BDDs (binary decision diagrams), e. g., in verification and for CAD problems, require an exact representation of the considered Boolean functions. However, if BDDs are used for learning Boolean functions f on the basis of classified examples (e. g., in the environment of genetic programming), it is sufficient to produce the representation of a function g approximating f . This motivates the investigation of the size of the smallest BDD approximating f . Here exponential lower bounds for several BDD variants are proved and the relations between the size of approximating BDDs, randomised BDDs, communication complexity and general approximation techniques are revealed.",
• notes = "see also doi:10.1006/inco.2002.3174",

}

Genetic Programming entries for Beate Bollig Martin Sauerhoff Ingo Wegener

Citations