A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions

Abstract

A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions is described. The method minimizes the number of functions forming the required superposition. The restriction on the number of arguments of the obtained functions is imposed. The method involves the specification of functions by interval form i. e. in the form of a pair of ternary matrices. One of the matrices represents intervals of Boolean space of the arguments (matrix of intervals), the other one represents the values of the functions at these intervals (matrix of functions). The graphs of rows orthogonality of those matrices are considered. The problem of functions decomposition is reduced to covering the edge set of the rows orthogonality graph of the matrix of functions by complete bipartite subgraphs (bicliques) of the row orthogonality graph of the matrix of intervals. Every biclique is assigned with a disjunctive normal form (DNF) by a certain way, and only those bicliques are taken into consideration whose DNFs have terms with the ranks not more than the bounds of the number of arguments of the obtained functions. The bicliques that form the desired cover and the cover itself are constructed sequentially by certain rules. Every biclique is used to construct the function whose arguments are the variables from the term of minimum rank from the corresponding DNF. The obtained functions are given also in interval form.