Tree-Shellability of Restricted DNFs

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• （社）電子情報通信学会の論文
• 2008-04-01

著者

• Takenaga Yasuhiko

  Department Of Computer Science The University Of Electro-communications

• KATOUGI Nao

  Department of Computer Science, the University of Electro-Communications

• Katougi Nao

  Department Of Computer Science The University Of Electro-communications

関連論文

• Tree-Shellability of Restricted DNFs

スポンサーリンク