Abstract:
The problem of parallel decomposition f (x) = j ( µ (u), l (v) ) of an incompletely specified Boolean function y = f (x) is regarded for arbitrary subsets u and v of the set of variables x. Seven possible properties of f (x) are formulated in terns of the three suggested models: bipartite graph, ternary matrix and mark functions. Revealing decomposability of f (x) and constructing proper Boolean functions j, µ and l are reduced to checking f (x) for these seven properties. A fast algorithm solving the problem is proposed and results of experiments are presented.