Implicit Representation and Manipulation of Binary Decision Diagrams

Hitoshi YAMAUCHI; Nagisa ISHIURA; Hiromitsu TAKAHASHI

Implicit Representation and Manipulation of Binary Decision Diagrams

Hitoshi YAMAUCHI, Nagisa ISHIURA, Hiromitsu TAKAHASHI

Full Text Views

0

Cite this

Summary :

This paper presents implicit representation of binary decision diagrams (implicit BDDs) as a new effecient data structure for Boolean functions. A well-known method of representing graphs by binary decision diagrams (BDDs) is applied to BDDs themselves. Namely, it is a BDD representation of BDDs. Regularity in the structure of BDDs representing certain Boolean functions contributes to significant reduction in size of the resulting implicit BDD repersentation. Since the implicit BDDs also provide canonical forms for Boolean functions, the equivalence of the two implicit BDD forms is decided in time proportional to the representation size. We also show an algorithm to maniqulate Boolean functions on this implicit data structure.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E79-A No.3 pp.354-362

Publication Date: 1996/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 8th Karuizawa Workshop on Circuits and Systems)

Category

Cite this

Copy

Hitoshi YAMAUCHI, Nagisa ISHIURA, Hiromitsu TAKAHASHI, "Implicit Representation and Manipulation of Binary Decision Diagrams" in IEICE TRANSACTIONS on Fundamentals, vol. E79-A, no. 3, pp. 354-362, March 1996, doi: .
Abstract: This paper presents implicit representation of binary decision diagrams (implicit BDDs) as a new effecient data structure for Boolean functions. A well-known method of representing graphs by binary decision diagrams (BDDs) is applied to BDDs themselves. Namely, it is a BDD representation of BDDs. Regularity in the structure of BDDs representing certain Boolean functions contributes to significant reduction in size of the resulting implicit BDD repersentation. Since the implicit BDDs also provide canonical forms for Boolean functions, the equivalence of the two implicit BDD forms is decided in time proportional to the representation size. We also show an algorithm to maniqulate Boolean functions on this implicit data structure.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e79-a_3_354/_p

Copy

@ARTICLE{e79-a_3_354,
author={Hitoshi YAMAUCHI, Nagisa ISHIURA, Hiromitsu TAKAHASHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Implicit Representation and Manipulation of Binary Decision Diagrams},
year={1996},
volume={E79-A},
number={3},
pages={354-362},
abstract={This paper presents implicit representation of binary decision diagrams (implicit BDDs) as a new effecient data structure for Boolean functions. A well-known method of representing graphs by binary decision diagrams (BDDs) is applied to BDDs themselves. Namely, it is a BDD representation of BDDs. Regularity in the structure of BDDs representing certain Boolean functions contributes to significant reduction in size of the resulting implicit BDD repersentation. Since the implicit BDDs also provide canonical forms for Boolean functions, the equivalence of the two implicit BDD forms is decided in time proportional to the representation size. We also show an algorithm to maniqulate Boolean functions on this implicit data structure.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Implicit Representation and Manipulation of Binary Decision Diagrams
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 354
EP - 362
AU - Hitoshi YAMAUCHI
AU - Nagisa ISHIURA
AU - Hiromitsu TAKAHASHI
PY - 1996
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E79-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1996
AB - This paper presents implicit representation of binary decision diagrams (implicit BDDs) as a new effecient data structure for Boolean functions. A well-known method of representing graphs by binary decision diagrams (BDDs) is applied to BDDs themselves. Namely, it is a BDD representation of BDDs. Regularity in the structure of BDDs representing certain Boolean functions contributes to significant reduction in size of the resulting implicit BDD repersentation. Since the implicit BDDs also provide canonical forms for Boolean functions, the equivalence of the two implicit BDD forms is decided in time proportional to the representation size. We also show an algorithm to maniqulate Boolean functions on this implicit data structure.
ER -