Tree-shellability of Boolean functions
In this paper, we define tree-shellable and ordered tree-shellable Boolean functions. A tree-shellable function is a positive Boolean function such that the number of prime implicants equals the number of paths from the root node to a I-node in its binary decision tree representation. A tree-shellable function is easy to dualize and good for a kind of reliability computation. We show their basic properties and clarify the relations between several shellable functions, i.e. shellable, tree-shellable, ordered tree-shellable, aligned and lexico-exchange functions. We also discuss on tree-shellable quadratic functions. (C) 2001 Elsevier Science B.V. All rights reserved.
boolean function prime implicant binary decision tree dualization shellability