IEICE TRANSACTIONS on Fundamentals
Implicit Representation and Manipulation of Binary Decision Diagrams
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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 -
English
