An Efficient State Minimization Algorithm for Some Special Classes of Incompletely Specified Sequential Machines

Author

Dunworth, A. ; Hartog, H.V.

Author_Institution

University of New South Wales

Issue

7

fYear

1979

fDate

7/1/1979 12:00:00 AM

Firstpage

531

Lastpage

535

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

Class-C; class-C1 machines; compatible and image-compatible classes; equivalence and image-equivalence classes; incompletely specified sequential machines; maximal compatibles; minimal covering machines; pairs-table analysis; Australia; Image analysis; Minimization methods; Sufficient conditions; Testing; Class-C; class-C1 machines; compatible and image-compatible classes; equivalence and image-equivalence classes; incompletely specified sequential machines; maximal compatibles; minimal covering machines; pairs-table analysis;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/TC.1979.1675400

Filename

1675400