Minimum self-dual decompositions of positive dual-minor Boolean functions

In this paper we consider decompositions of a positive dual-minor Boolean f unction f into f = f(1)f(2),...,f(k), where all f, are positive and self-du al. It is shown that the minimum k having such a decomposition equals the c hromatic number of a graph associated with f, and the problem of deciding w hether a decomposition of size k exists is co-NP-hard, for k greater than o r equal to 2. We also consider the canonical decomposition of f and show th at the complexity of finding a canonical decomposition is equivalent to dec iding whether two positive Boolean functions are mutually dual. Finally, fo r the class of path functions including the class of positive read-once fun ctions, we show that the sizes of minimum decompositions and minimum canoni cal decompositions are equal, and present a polynomial total time algorithm to generate all minimal canonical decompositions. (C) 1999 Elsevier Scienc e B.V. All rights reserved.