J. J. Lou and J. A. Brzozowski

Department of Computer Science

University of Waterloo

Waterloo, Ontario

Canada N2L 3G1

February, 1998

** Abstract **

We consider two methods for the decomposition of Boolean and multi-valued
functions into

functions with fewer arguments. Shestakov's method (which we call "double
decomposition")

expresses a function f(x_1,...,x_n) as a composite function
h(g_1(u_1,...,u_r),g_2(v_1,...,v_s)),

where the union of
U={u_1,...,u_r} and V={v_1,...,v_s} is the set
X={x_1,...,x_n}. The

independently developed method of Luba and Selvaraj (which we call
"single decomposition")

expresses a function f(x_1,...,x_n) as a composite function
h(u_1,...,u_r,g(v_1,...,v_s)).

The latter method has been formalized by Brzozowski
and Luba using ``blankets,''
which are

generalizations of set systems. In this paper, we use the same blanket
approach to
formalize

Shestakov's decomposition method. We compare the two methods, and verify
that double

decomposition is
equivalent to two steps of single decomposition.
Recently, Brzozowski and Lou

extended the single decomposition methods
to multi-valued functions.
Using the same approach,

we also extend
Shestakov's method to the multi-valued case.

This research was supported by the Natural Sciences and Engineering
Research

Council of Canada under grant No. OGP0000871 and a postgraduate scholarship.