This paper addresses the problem of finding attractors in synchronous Boolean networks. The existing Boolean decision diagram-based algorithms have limited capacity due to the excessive memory requirements of decision diagrams. The simulation-based algorithms can be applied to larger networks, however, they are incomplete. We present an algorithm, which uses a SAT-based bounded model checking to find all attractors in a Boolean network. The efficiency of the presented algorithm is evaluated by analyzing seven networks models of real biological processes, as well as 150,000 randomly generated Boolean networks of sizes between 100 and 7,000. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.

Non-linear feedback shift registers (NLFSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for generating pseudo-random sequences for stream ciphers. In this paper, we introduce (n,k)-NLFSRs which can be considered a generalization of the Galois type of LFSR. In an (n,fc)-NLFSR, the feedback can be taken from any of the n bits, and the next state functions can be any Boolean function of up to k variables. Our motivation for considering this type NLFSRs is that their Galois configuration makes it possible to compute each next state function in parallel, thus increasing the speed of output sequence generation. Thus, for stream cipher application where the encryption speed is important, (n,k)-NLFSRs may be a better alternative than the traditional Fibonacci ones. We derive a number of properties of (n,k)- NLFSRs. First, we demonstrate that they are capable of generating output sequences with good statistical properties which cannot be generated by the Fibonacci type of NLFSRs. Second, we show that the period of the output sequence of an (n,k)-NLFSR is not necessarily equal to the length of the largest cycle of its states. Third, we compute the period of an (n,k)-NLFSR constructed from several parallel NLFSRs whose outputs are XOR-ed and show how to maximize this period. We also present an algorithm for estimating the length of cycles of states of (n,k)-NLFSRs which uses binary decision diagrams for representing the set of states and the transition relation on this set.

Graph dominators provide a general mechanism for identifying re-converging paths in circuits. This is useful in a number of CAD applications, including computation of signal probabilities for test generation, switching activities for power and noise analysis, statistical timing analysis, cut point selection in equivalence checking, etc. Single-vertex dominators are too rare in circuit graphs to handle re-converging paths in a practical way. The paper addresses the problem of finding double-vertex dominators, which occur more frequently. First, we introduce a data structure, called dominator chain, which allows the representation of all possible O(n/sup 2/) double-vertex dominators of a given vertex in O(n) space, where n is the number of vertices of the circuit graph. Dominator chains can be efficiently manipulated, e.g., it takes constant time to look-up whether a given pair of vertices is a double-vertex dominator. Second, we present an efficient algorithm for finding double-vertex dominators. The experimental results show that the presented algorithm is an order of magnitude faster than existing algorithms for finding double-vertex dominators. Thus, it is suitable for running in an incremental manner during logic synthesis.

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 work presents Hermes, a depth-optimal LUT based FPGA mapping algorithm. The presented algorithm is based on a new strategy for finding LUTs allowing to find a good LUT in a significantly shorter time compared to the previous methods. The quality of results is improved by enabling LUT re-implementation and by introducing a cost function which encourages input sharing among LUTs. The experimental results show that, on average, the presented algorithm computes 15.5% and 3.5% smaller LUT mappings compared to the ones obtained by FlowMap and CutMap, respectively, using two orders of magnitude less CPU time. The speed of Hermes makes it suitable for running in an incremental manner during logic synthesis.

We present a new algorithm for decomposition of type f=g/spl middot/h+r. The algorithm searches for Boolean products g/spl middot/h of a special type, called cyclic chains. The number of cubes in a cyclic chain is no greater than the number of cubes in the part of the on-set of f covered by this chain. The number of literals is always smaller. Cyclic chains are extracted recursively until no more can be found. The presented algorithm is of particular interest in applications, which require circuit representations of a limited depth. Experimental results on benchmark circuits demonstrate the efficiency of our approach.