Title: The state reduction of nondeterministic finite-state machines
Abstract: Nondeterministic finite-state machines (NFSM's) are a powerful tool for specifying the desired behavior of a sequential system along with its degrees of freedom. Moreover, nondeterministic machines arise naturally when considering the optimization problem of interacting synchronous circuits or deterministic finite-state machines. Yet, NFSM's have been considered only recently in the literature. In this paper, we present algorithms for synthesizing a minimum state implementation of a specification NFSM. The algorithm is a generalization of the classical method for incompletely specified machines, with several modifications. We also introduce the notion of equivalence between compatibility classes and a novel formulation of the closure problem to eliminate unnecessary classes and implications, so as to speed up substantially the search of the optimum solution. A novel BDD-based implementation technique is also presented, which avoids the explicit representation of the transition relation of the original NFSM.
Publication Year: 1997
Publication Date: 1997-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 8
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot