A new algorithm for exact reduction of incompletely specified finite state machines

We propose a new algorithm for the problem of state reduction in incompletely specified finite state machines. Unlike the most commonly used algorithms for this problem, our approach is not based on the enumeration of compatible sets, and, therefore, its performance is not dependent on its number. I...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computer-aided design of integrated circuits and systems 1999-11, Vol.18 (11), p.1619-1632
Main Authors: Pena, J.M., Oliveira, A.L.
Format: Article
Language:English
Subjects:
Algorithms
Automata
Circuit synthesis
Compatibility
Computer aided design
Computer science
Design engineering
Doped fiber amplifiers
Enumeration
Finite state machines
Heuristic algorithms
Informatics
Integrated circuits
Laboratories
Polynomials
Sequential circuits
State reduction
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a new algorithm for the problem of state reduction in incompletely specified finite state machines. Unlike the most commonly used algorithms for this problem, our approach is not based on the enumeration of compatible sets, and, therefore, its performance is not dependent on its number. Instead, the algorithm uses techniques for finite state machine identification that are well known in the computer science literature, but have never been applied to this problem. 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. We also present a complexity analysis for the special cases where worst case polynomial time bounds can be obtained and present experiments that validate empirically the bounds obtained.
ISSN:0278-0070
1937-4151
DOI:10.1109/43.806807