The search functionality is under construction.

The search functionality is under construction.

In this paper, we consider the complexity of recognizing ordered tree-shellable Boolean functions when Boolean functions are given as OBDDs. An ordered tree-shellable function is a positive Boolean function such that the number of prime implicants equals the number of paths from the root node to a 1-node in its ordered binary decision tree representation. We show that given an OBDD, it is possible to check within polynomial time if the function is ordered tree-shellable with respect to the variable ordering of the OBDD.

- Publication
- IEICE TRANSACTIONS on Information Vol.E84-D No.1 pp.28-33

- Publication Date
- 2001/01/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Issue on Selected Papers from LA Symposium)

- Category

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.

Copy

Yasuhiko TAKENAGA, "Recognition of Ordered Tree-Shellable Boolean Functions Based on OBDDs" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 1, pp. 28-33, January 2001, doi: .

Abstract: In this paper, we consider the complexity of recognizing ordered tree-shellable Boolean functions when Boolean functions are given as OBDDs. An ordered tree-shellable function is a positive Boolean function such that the number of prime implicants equals the number of paths from the root node to a 1-node in its ordered binary decision tree representation. We show that given an OBDD, it is possible to check within polynomial time if the function is ordered tree-shellable with respect to the variable ordering of the OBDD.

URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_1_28/_p

Copy

@ARTICLE{e84-d_1_28,

author={Yasuhiko TAKENAGA, },

journal={IEICE TRANSACTIONS on Information},

title={Recognition of Ordered Tree-Shellable Boolean Functions Based on OBDDs},

year={2001},

volume={E84-D},

number={1},

pages={28-33},

abstract={In this paper, we consider the complexity of recognizing ordered tree-shellable Boolean functions when Boolean functions are given as OBDDs. An ordered tree-shellable function is a positive Boolean function such that the number of prime implicants equals the number of paths from the root node to a 1-node in its ordered binary decision tree representation. We show that given an OBDD, it is possible to check within polynomial time if the function is ordered tree-shellable with respect to the variable ordering of the OBDD.},

keywords={},

doi={},

ISSN={},

month={January},}

Copy

TY - JOUR

TI - Recognition of Ordered Tree-Shellable Boolean Functions Based on OBDDs

T2 - IEICE TRANSACTIONS on Information

SP - 28

EP - 33

AU - Yasuhiko TAKENAGA

PY - 2001

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E84-D

IS - 1

JA - IEICE TRANSACTIONS on Information

Y1 - January 2001

AB - In this paper, we consider the complexity of recognizing ordered tree-shellable Boolean functions when Boolean functions are given as OBDDs. An ordered tree-shellable function is a positive Boolean function such that the number of prime implicants equals the number of paths from the root node to a 1-node in its ordered binary decision tree representation. We show that given an OBDD, it is possible to check within polynomial time if the function is ordered tree-shellable with respect to the variable ordering of the OBDD.

ER -