DECOMPOSITIONS OF POSITIVE SELF-DUAL BOOLEAN FUNCTIONS

A coterie, which is used to realize mutual exclusion in distributed systems, is a family C of subsets such that any pair of subsets in C has at least one element in common, and such that no subset in C contains any other subset in C. Associate with a family of subsets C a positive Boolean function f(c) such that f(c)(x) = 1 if the Boolean vector x is equal to or greater than the characteristic vector of some subset in C, and 0 otherwise. It is known that C is a coterie if and only if f(c) is dual-minor, and is a non-dominated (ND) coterie if and only if f(c) is self-dual. We study in this paper the decomposition of a positive self-dual function into smaller positive self-dual functions, as it explains how to represent and how to construct the corresponding ND coterie. A key step is how to decompose a positive dual-minor function f into a conjunction of positive self-dual functions f(1),f(2),...,f(k). In addition to the general condition for this decomposition, we clarify the condition for the decomposition into two functions f(1) and f(2), and introduce the concept of canonical decomposition. Then we present an algorithm that determines a minimal canonical decomposition, and a very simple algorithm that usually gives a decomposition close to minimal. The decomposition of a general self-dual function is also discussed.