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

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

  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",
  language =     "en",
  oai =          "oai:CiteSeerX.psu:",
  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
  URL =          "",
  URL =          "",
  broken =       "",
  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