
Blanket Algebra for Decomposition of FunctionsAbstract
We consider the decomposition of multiplevalued partially specified
functions. Such a function f has n inputs, x1, x2, ... xn, each input
taking values from a finite set E, and m outputs, y1, y2 ... ym, which
are only partially specified. Let D be the set of all nonempty
subsets of E. In general, f assigns to any output yi a nonempty set d
(in D) of elements of E. if d = {e} for some e in E, then yi has the
value e. If d = E, then yi is a "complete dont care", i.e., is allowed
to take on any value in E.
In other cases, yi is a "limited dont 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)
in the form h(U, g(V)), where X = {x1, ... xn} is the set of input
variables, U and V 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 talk we extend blanket algebra
methods to the decomposition of multivalued set functions.
Relevant PapersJ. J. Lou and J. A. Brzozowski, "A Formalization of Shestakov's Decomposition" , Research Report, University of Waterloo.J. A. Brzozowski and T. Luba, "Decomposition of Boolean Functions Specified by Cubes" , Research Report, University of Waterloo. J. A. Brzozowski and J. J. Lou, "Blanket Algebra for MultipleValued Function Decomposition" , Proceedings of the International Workshop on Formal Languages and Computer Systems, Kyoto, Japan, 1997.
Transparenciesavailable here .

Contact 
©20022018 U.C. Regents 