Finding compact BDDs using genetic programming

Ulrich Kühne; Nicole Drechsler

doi:10.1007/11732242_28

Finding compact BDDs using genetic programming

Ulrich Kühne, Nicole Drechsler

University of Bremen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Binary Decision Diagrams (BDDs) can be used to design multiplexor based circuits. Unfortunately, the most commonly used kind of BDDs - ordered BDDs - has exponential size in the number of variables for many functions. In some cases, more general forms of BDDs are more compact. In constrast to the minimization of OBDDs, which is well understood, there are no heuristics for the construction of compact BDDs up to today. In this paper we show that compact BDDs can be constructed using Genetic Programming.

Original language	English
Title of host publication	Applications of Evolutionary Computing - EvoWorkshops 2006
Subtitle of host publication	EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Proceedings
Publisher	Springer Verlag
Pages	308-319
Number of pages	12
ISBN (Print)	3540332375, 9783540332374
DOIs	https://doi.org/10.1007/11732242_28
Publication status	Published - 1 Jan 2006
Externally published	Yes
Event	EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC - Budapest, Hungary Duration: 10 Apr 2006 → 12 Apr 2006

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	3907 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC
Country/Territory	Hungary
City	Budapest
Period	10/04/06 → 12/04/06

Access to Document

10.1007/11732242_28

Cite this

Kühne, U., & Drechsler, N. (2006). Finding compact BDDs using genetic programming. In Applications of Evolutionary Computing - EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Proceedings (pp. 308-319). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3907 LNCS). Springer Verlag. https://doi.org/10.1007/11732242_28

Kühne, Ulrich ; Drechsler, Nicole. / Finding compact BDDs using genetic programming. Applications of Evolutionary Computing - EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Proceedings. Springer Verlag, 2006. pp. 308-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b13055ea062e49bfaa01b4b42f21f91a,

title = "Finding compact BDDs using genetic programming",

abstract = "Binary Decision Diagrams (BDDs) can be used to design multiplexor based circuits. Unfortunately, the most commonly used kind of BDDs - ordered BDDs - has exponential size in the number of variables for many functions. In some cases, more general forms of BDDs are more compact. In constrast to the minimization of OBDDs, which is well understood, there are no heuristics for the construction of compact BDDs up to today. In this paper we show that compact BDDs can be constructed using Genetic Programming.",

author = "Ulrich K{\"u}hne and Nicole Drechsler",

year = "2006",

month = jan,

day = "1",

doi = "10.1007/11732242\_28",

language = "English",

isbn = "3540332375",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "308--319",

booktitle = "Applications of Evolutionary Computing - EvoWorkshops 2006",

note = "EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC ; Conference date: 10-04-2006 Through 12-04-2006",

}

Kühne, U & Drechsler, N 2006, Finding compact BDDs using genetic programming. in Applications of Evolutionary Computing - EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3907 LNCS, Springer Verlag, pp. 308-319, EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Budapest, Hungary, 10/04/06. https://doi.org/10.1007/11732242_28

Finding compact BDDs using genetic programming. / Kühne, Ulrich; Drechsler, Nicole.
Applications of Evolutionary Computing - EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Proceedings. Springer Verlag, 2006. p. 308-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3907 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Finding compact BDDs using genetic programming

AU - Kühne, Ulrich

AU - Drechsler, Nicole

PY - 2006/1/1

Y1 - 2006/1/1

N2 - Binary Decision Diagrams (BDDs) can be used to design multiplexor based circuits. Unfortunately, the most commonly used kind of BDDs - ordered BDDs - has exponential size in the number of variables for many functions. In some cases, more general forms of BDDs are more compact. In constrast to the minimization of OBDDs, which is well understood, there are no heuristics for the construction of compact BDDs up to today. In this paper we show that compact BDDs can be constructed using Genetic Programming.

AB - Binary Decision Diagrams (BDDs) can be used to design multiplexor based circuits. Unfortunately, the most commonly used kind of BDDs - ordered BDDs - has exponential size in the number of variables for many functions. In some cases, more general forms of BDDs are more compact. In constrast to the minimization of OBDDs, which is well understood, there are no heuristics for the construction of compact BDDs up to today. In this paper we show that compact BDDs can be constructed using Genetic Programming.

U2 - 10.1007/11732242_28

DO - 10.1007/11732242_28

M3 - Conference contribution

AN - SCOPUS:33745768133

SN - 3540332375

SN - 9783540332374

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 308

EP - 319

BT - Applications of Evolutionary Computing - EvoWorkshops 2006

PB - Springer Verlag

T2 - EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC

Y2 - 10 April 2006 through 12 April 2006

ER -

Kühne U, Drechsler N. Finding compact BDDs using genetic programming. In Applications of Evolutionary Computing - EvoWorkshops 2006: EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoINTERACTION, EvoMUSART, and EvoSTOC, Proceedings. Springer Verlag. 2006. p. 308-319. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/11732242_28

Finding compact BDDs using genetic programming

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this