Minimum self-dual decompositions of positive dual-minor Boolean functions Original Research Article

In this paper we consider decompositions of a positive dual-minor Boolean function f into f=f1f2,…,fk, where all fj are positive and self-dual. It is shown that the minimum k having such a decomposition equals the chromatic number of a graph associated with f, and the problem of deciding whether a decomposition of size k exists is co-NP-hard, for k⩾2. We also consider the canonical decomposition of f and show that the complexity of finding a canonical decomposition is equivalent to deciding whether two positive Boolean functions are mutually dual. Finally, for the class of path functions including the class of positive read-once functions, we show that the sizes of minimum decompositions and minimum canonical decompositions are equal, and present a polynomial total time algorithm to generate all minimal canonical decompositions.