IEICE Transactions on Information and Systems

IEICE Transactions on Information and Systems 2008 E91-D(4):996-1002; doi:10.1093/ietisy/e91-d.4.996

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by TAKENAGA, Y. Articles by KATOUGI, N. Social Bookmarking          What's this?

Copyright © 2008 The Institute of Electronics, Information and Communication Engineers

Regular Section -- Papers -- Algorithm Theory

Tree-Shellability of Restricted DNFs

Yasuhiko TAKENAGA¹ and Nao KATOUGI^1,2

¹ The authors are with the Department of Computer Science, the University of Electro-Communications, Chofu-shi, 182–8585 Japan. E-mail: takenaga{at}cs.uec.ac.jp, ² Presently, the author is with NEC Corporation.

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 k². 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.

Key Words: Boolean function, shellability, prime implicant, binary decision tree

---

Manuscript received May 31, 2007. Manuscript revised October 24, 2007.

Reference

[1] M.O. Ball and G.L. Nemhauser, "Matroids and a reliability analysis problem," Math. Oper. Res., vol.4, pp.132–143, 1979.

[2] M.O. Ball and J.S. Provan, "Disjoint products and efficient computation of reliability," Oper. Res., vol.36, no.5, pp.703–715, 1988.

[3] J.C. Bioch and T. Ibaraki, "Complexity of identification and dualization of positive Boolean functions," Inf. Comput., vol.123, no.1, pp.50–63, 1995.

[4] E. Boros, Y. Crama, O. Ekin, P.L. Hammer, T. Ibaraki, and A. Kogan, "Boolean normal forms, shellability and reliability computations," SIAM J. Discrete Math., vol.13, no.2, pp.212–226, 2000.

[5] H. Brugesser and P. Mani, "Shellable decompositions of cells and spheres," Math. Scand., vol.29, pp.199–205, 1971.

[6] G. Danaraj and V. Klee, "Shellings of spheres and polytopes," Duke Math. J., vol.41, pp.443–451, 1974.

[7] C. Domingo, N. Mishra, and L. Pitt, "Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries," Mach. Learn., vol.37, pp.89–110, 1999.

[8] M.L. Fredman and L. Khachiyan, "On the complexity of dualization of monotone disjunctive normal forms," J. Algorithms, vol.21, no.3, pp.618–628, 1996.

[9] J.S. Provan and M.O. Ball, "Efficient recognition of matroids and 2-monotonic systems," in Applications of Discrete Mathematics, eds. R. Ringeisen and F. Roberts, pp.122–134, SIAM, Philadelphia, 1988.

[10] Y. Takenaga, K. Nakajima, and S. Yajima, "Tree-shellability of Boolean functions," Theor. Comput. Sci., vol.262, no.2, pp.633–647, 2001.

CiteULike    Connotea    Del.icio.us    What's this?

This Article Abstract Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to My Personal Archive Download to citation manager Request Permissions Google Scholar Articles by TAKENAGA, Y. Articles by KATOUGI, N. Social Bookmarking          What's this?