Blanket Algebra for Multiple-Valued Function Decomposition

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.