2004 · 25 citations · 25 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureFormal MethodsDigital Logic DesignFinite State Machine ModelingLogic SynthesisModel CheckingPetri NetsAsynchronous Sequential CircuitsBoolean SatisfiabilityBoolean Satisfiability ProblemPetri Net Model CheckingSatisfiabilityState Space ExplorationState Space ExplosionState-space Reduction
The behaviour of asynchronous circuits is often described by signal transition graphs (STGs), which are Petri nets whose transitions are interpreted as rising and falling edges of signals. One of the crucial problems in the synthesis of such circuits is that of identifying whether an STG satisfies the complete state coding (CSC) requirement, e.g., by using model checking based on the state graph of an STG. We avoid constructing the state graph of an STG, which can lead to state space explosion, and instead use only the information about causality and structural conflicts between the events involved in a finite and complete prefix of its unfolding. The algorithm is derived by adopting the boolean satisfiability (SAT) approach. This technique leads not only to huge memory savings when compared to methods based on state graphs, but also to significant speedups.
25
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
Matthew W. Moskewicz, Conor Madigan, Ying Zhao et al. · 2001 · 2.9K citations