| 講演抄録／キーワード |
| 講演名 |
2005-05-20 13:30
リテラルの出現回数に制限を加えたTree-Shellable論理関数の判定複雑さ
○加藤木 直・武永康彦（電通大） |
| 抄録 |
（和） |
Tree-shellable論理関数とは、根のノードから１にラベル付けされた葉ノードへのパスの数が、主項の数と同じになるような二分木表現を持つ正論理関数である。本稿では、積和形論理式で与えられた関数中の同一変数の出現回数とtree-shellabilityに関する性質を明らかにする。
またそれを用い、リテラルの出現回数に制限を加えた場合の、(ordered) tree-shellableであるか否かを判定する問題の複雑さ明らかにする。
本稿のアルゴリズムにより、同一リテラルの出現回数が高々定数の場合、tree-shellable論理関数、ordered tree-shellable論理関数の判定がともに多項式時間で実行できる。 |
| （英） |
A tree-shellable function is a positive Boolean function which can be representation by a binary decision tree such that the number of prime implicants equals the number of paths from the root to a leaf labeled 1 in its binary decision tree representation. In this paper, we show that the maximum number of the same literal in a DNF is related to tree-shellability. By using the results, if the same literal appears at most constant times, tree-shellability and ordered tree-shellability can be checked in polynomial time. |
| キーワード |
（和） |
論理関数 / 二分決定木 / 主項 / tree-shellability / / / / |
| （英） |
Boolean function / binary decision tree / prime implicant / tree-shellability / / / / |
| 文献情報 |
信学技報, vol. 105, no. 72, COMP2005-12, pp. 25-30, 2005年5月. |
| 資料番号 |
COMP2005-12 |
| 発行日 |
2005-05-13 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|