J. A. Brzozowski and J. J. Lou

Department of Computer Science

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

June 1997

Revised February 12, 1998

** Abstract **

We consider functions of the form f: E^n -> D^m, where n, m > 0 are

integers, E is a finite, nonempty set, and D = 2^E - {emptyset}.

Such a function has n inputs, x_1,...,x_n, each input taking values

from E, and m outputs, y_1,...,y_m, which are only partially specified.

In general, f assigns to any output y_i a nonempty set d in D of

elements of E. If d = {e} for some e in E, then y_i has the value e.

If d = E, then y_i is a "complete don't care," i.e., is allowed to

take on any value in E. In other cases, y_i is a "limited don't care"

allowed to take on any value in d. Moreover, the functions are

represented in a compact notation, which is a generalization of the

cube notation for Boolean functions. In this representation, we call

these functions "set functions." We consider the problem of decomposing

a set function f(x_1,...,x_n) in the form h(u_1,...,u_r,g(v_1,...,v_s)),

where X = {x_1,...,x_n} is the set of input variables, U = {u_1,...,u_r}

and V = {v_1,...,v_s} are two subsets of X whose union is X, and g and h

are set functions. It has been previously shown that Boolean function

decompositions can be obtained with the aid of blankets, which

are a generalization of set systems. In this paper we extend blanket

algebra methods to the decomposition of multiple-valued set functions.

This research was supported by the Natural Sciences and Engineering

Research Council of Canada under grant No. OGP0000871.