IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1993 · 21 citations · 26 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureTheory Of ComputationCircuit ComplexityComputational ComplexityFinite-state MachinesHeuristic ComputationLower Bound TechniquesPruningSearch Space PruningSequential MachinesState MachinesState MinimizationState Space Search
The removal of redundant states in a finite state machine (FSM) is essential to reducing the complexity of a sequential circuit. An efficient algorithm for state minimization in incompletely specified state machines is presented. This algorithm employs a tight lower bound and a fail-first heuristic and generates a relatively small search space from the prime compatibles. It utilizes efficient pruning rules to further reduce the search space and finds a minimal closed cover. The technique guarantees the elimination of all the redundant states in a very short execution time. Experimental results with a large number of FSMs including the MCNC FSM benchmarks are presented. The results are compared with other work in this area.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
26
Algebraic structure theory of sequential machines
John E. Hopcroft · Journal of the Franklin Institute · 1967 · 380 citations