IEICE TRANSACTIONS on Information
Recognition of Ordered Tree-Shellable Boolean Functions Based on OBDDs
Summary :
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
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
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 -
English
