リテラルの出現回数に制限を加えたTree-Shellable論理関数の判定複雑さ  [in Japanese] Recognition of Tree-Shellable Boolean Functions with Restrictions to the Number of the Same Literal  [in Japanese]

Tree-shellable論理関数とは、根のノードから1にラベル付けされた葉ノードへのパスの数が、主項の数と同じになるような二分木表現を持つ正論理関数である。本稿では、積和形論理式で与えられた関数中の同一変数の出現回数と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.