Blanket Algebra for Decomposition of Functions

Abstract

We consider the decomposition of multiple-valued 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 multi-valued set functions.

Relevant Papers

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 Multiple-Valued Function Decomposition" , Proceedings of the International Workshop on Formal Languages and Computer Systems, Kyoto, Japan, 1997.

Transparencies