J. J. Lou,
Decomposition of Multi-Valued Functions,
MMath Thesis,
Department of Computer Science,
University of Waterloo, Waterloo, Ontario, Canada N2L 3G1,
August 1998.
(Supervised by J. A. Brzozowski)

Abstract

Decomposition of functions has been studied since the late 1950s; it was mainly
used in minimizing circuit designs for switching functions. Recently, decompositions
have been used in FPGA synthesis and other applications, and interest in this topic has
again increased. A commonly used method decomposes a function f(x_1,...,x_n) into
the form h(x_1,...,x_r,g(x_{r+1},...,x_n)), where both g and h are switching functions.
In this thesis, we study the decomposition of a very general form of functions,
called set functions , using this approach. Set functions are multi-valued
functions where the outputs can take the value of any non-empty subset of an underlying
set E. We represent these functions in a compact cube notation using consistent
set matrices
. A decomposition theory of such functions is presented using blankets,
which are a generalization of partitions and set systems. We also give a survey of different decomposition methods, including the formalizations of some of these methods using blankets.