IEICE TRANSACTIONS on Information
Tree-Shellability of Restricted DNFs
Summary :
A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime implicants. In this paper, we consider the tree-shellability of DNFs with restrictions. We show that, for read-k DNFs, the number of terms in a tree-shellable function is at most k2. We also show that, for k-DNFs, recognition of ordered tree-shellable functions is NP-complete for k=4 and tree-shellable functions can be recognized in polynomial time for constant k.
- Publication
- IEICE TRANSACTIONS on Information Vol.E91-D No.4 pp.996-1002
- Publication Date
- 2008/04/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e91-d.4.996
- Type of Manuscript
- PAPER
- Category
- Algorithm Theory
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, Nao KATOUGI, "Tree-Shellability of Restricted DNFs" in IEICE TRANSACTIONS on Information,
vol. E91-D, no. 4, pp. 996-1002, April 2008, doi: 10.1093/ietisy/e91-d.4.996.
Abstract: A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime implicants. In this paper, we consider the tree-shellability of DNFs with restrictions. We show that, for read-k DNFs, the number of terms in a tree-shellable function is at most k2. We also show that, for k-DNFs, recognition of ordered tree-shellable functions is NP-complete for k=4 and tree-shellable functions can be recognized in polynomial time for constant k.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e91-d.4.996/_p
Copy
@ARTICLE{e91-d_4_996,
author={Yasuhiko TAKENAGA, Nao KATOUGI, },
journal={IEICE TRANSACTIONS on Information},
title={Tree-Shellability of Restricted DNFs},
year={2008},
volume={E91-D},
number={4},
pages={996-1002},
abstract={A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime implicants. In this paper, we consider the tree-shellability of DNFs with restrictions. We show that, for read-k DNFs, the number of terms in a tree-shellable function is at most k2. We also show that, for k-DNFs, recognition of ordered tree-shellable functions is NP-complete for k=4 and tree-shellable functions can be recognized in polynomial time for constant k.},
keywords={},
doi={10.1093/ietisy/e91-d.4.996},
ISSN={1745-1361},
month={April},}
Copy
TY - JOUR
TI - Tree-Shellability of Restricted DNFs
T2 - IEICE TRANSACTIONS on Information
SP - 996
EP - 1002
AU - Yasuhiko TAKENAGA
AU - Nao KATOUGI
PY - 2008
DO - 10.1093/ietisy/e91-d.4.996
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E91-D
IS - 4
JA - IEICE TRANSACTIONS on Information
Y1 - April 2008
AB - A tree-shellable function is a positive Boolean function which can be represented by a binary decision tree whose number of paths from the root to a leaf labeled 1 equals the number of prime implicants. In this paper, we consider the tree-shellability of DNFs with restrictions. We show that, for read-k DNFs, the number of terms in a tree-shellable function is at most k2. We also show that, for k-DNFs, recognition of ordered tree-shellable functions is NP-complete for k=4 and tree-shellable functions can be recognized in polynomial time for constant k.
ER -
English
