DocumentCode
2521490
Title
A new algorithm for the reduction of incompletely specified finite state machines
Author
Pena, J.M. ; Oliveira, A.L.
Author_Institution
IST, INESC, Lisbon, Portugal
fYear
1998
fDate
8-12 Nov. 1998
Firstpage
482
Lastpage
489
Abstract
We propose an algorithm for the problem of state reduction in incompletely specified finite state machines. This algorithm is not based on the enumeration of compatible sets, and therefore, its performance is not dependent on the number of prime compatibles. We prove that the algorithm is exact and present results that show that, in a set of hard problems, it is much more efficient than both the explicit and implicit approaches based on the enumeration of compatible sets.
Keywords
computational complexity; finite state machines; logic CAD; sequential circuits; compatible set enumeration; hard problems; incompletely specified finite state machines; prime compatibles; state reduction; Automata; Circuit synthesis; Computer science; Doped fiber amplifiers; Permission; Polynomials; Sequential circuits;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer-Aided Design, 1998. ICCAD 98. Digest of Technical Papers. 1998 IEEE/ACM International Conference on
Conference_Location
San Jose, CA, USA
Print_ISBN
1-58113-008-2
Type
conf
DOI
10.1109/ICCAD.1998.144312
Filename
742956
Link To Document