This paper addresses two problems related to disjoint-support decomposition of Boolean functions. First, we present a heuristic for finding a subset of variables, X, which results in the disjoint-support decomposition f(X, Y)=h(g(X), Y) with a good area/delay trade-off. Second, we present a technique for re-synthesis of the original circuit, implementing f(X, Y) into a circuit implementing the decomposed representation h(g(X), Y). Preliminary experimental results indicate that the proposed approach has significant potential.

A Kauffman network is an abstract model of gene regulatory networks. Each gene is represented by a vertex. An edge from one vertex to another implies that the former gene regulates the latter. Statistical features of Kauffman networks match the characteristics of living cells. The number of cycles in the network's state space, called attractors, corresponds to the number of different cell types. The attractor's length corresponds to the cell cycle time. The sensitivity of attractors to different kinds of disturbances, modeled by changing a network connection, the state of a vertex, or the associated function, reflects the stability of the cell to damage, mutations and virus attacks. In order to evaluate attractors, their number and lengths have to be computed. This problem is the major open problem related to Kauffman networks. Available algorithms can only handle networks with less than a hundred vertices. The number of genes in a cell is often larger. In this paper, we present a set of efficient algorithms for computing attractors in large Kauffman networks. The resulting software package is hoped to be of assistance in understanding the principles of gene interactions and discovering a computing scheme operating on these principles.

This paper reports a result concerning the relation between the best variable orderings of an ROBDD G/sub f/ and the decomposition structure of the Boolean function f represented by G/sub f/. It was stated in [S.-W. Jeong (1992)] that, if f has a decomposition of type f(X)-g(h/sub 1/(Y/sub 1/),h/sub 2/(Y/sub 2/),...h/sub k/(Y/sub k/)), where {Y/sub 1/}, i/spl isin/{1,2,...,k}, is a partition of X, then one of the orderings which keeps the variables within the sets {Y/sub 1/} adjacent is a best ordering for G/sub f/. Using a counterexample, we show that this statement is incorrect.

This paper presents a heuristic algorithm for disjoint decomposition of a Boolean function based on its ROBDD representation. Two distinct features make the algorithm feasible for large functions. First, for an n-variable function, it checks only O(n2) candidates for decomposition out of O(2n) possible ones. A special strategy for selecting candidates makes it likely that all other decompositions are encoded in the selected ones. Second, the decompositions for the approved candidates are computed using a novel IntervalCut algorithm. This algorithm does not require re-ordering of ROBDD. The combination of both techniques allows us to decompose the functions of size beyond that possible with the exact algorithms. The experimental results on 582 benchmark functions show that the presented heuristic finds 95% of all decompositions on average. For 526 of those functions, it finds 100% of the decompositions.