An Efficient State Minimization Algorithm for Some Special Classes of Incompletely Specified Sequential Machines
- 1 July 1979
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-28 (7) , 531-535
- https://doi.org/10.1109/tc.1979.1675400
Abstract
Two classes of incompletely specified sequential machine (ISSM) are described, which contain the class of input-restricted machines defined by McCluskey [1] and Unger [2] as special cases. These new classes of machine can be identified at the conclusion of a modified (and more efficient) version of the standard compatible pairs-table analysis of Paull and Unger [3]. For such machines only maximal compatible classes need be considered in finding the minimal state machine, and any such covering selection is also closed. An algorithm is presented which is fast and efficient both for hand-use and computer implementation.Keywords
This publication has 6 references indexed in Scilit:
- Minimization of Incompletely Specified Sequential MachinesIEEE Transactions on Computers, 1975
- A Note on State Minimization of a Special Class of Incomplete Sequential MachinesIEEE Transactions on Computers, 1972
- A Method for Minimizing the Number of Internal States in Incompletely Specified Sequential NetworksIEEE Transactions on Electronic Computers, 1965
- Flow Table Simplification-Some Useful AidsIEEE Transactions on Electronic Computers, 1965
- Minimum-State Sequential Circuits for a Restricted Class of Incompletely Specified Flow Tables*Bell System Technical Journal, 1962
- Minimizing the Number of States in Incompletely Specified Sequential Switching FunctionsIEEE Transactions on Electronic Computers, 1959