A Formalization of Shestakov's Decomposition

J. J. Lou and J. A. Brzozowski

Research Report CS-98-03
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.