Some dangers in state reduction of sequential machines

In this paper we investigate the negative effects of state reduction on the realization of a sequential machine. It is shown that state reduction can destroy realizations of a given sequential machine from sets of smaller machines and thus lead to a sequential machine that is harder to realize. To u...

Full description

Saved in:
Bibliographic Details
Published in:Information and control 1962-01, Vol.5 (3), p.252-260
Main Authors: Hartmanis, J., Stearns, R.E.
Format: Article
Language:English
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:In this paper we investigate the negative effects of state reduction on the realization of a sequential machine. It is shown that state reduction can destroy realizations of a given sequential machine from sets of smaller machines and thus lead to a sequential machine that is harder to realize. To understand some of the reasons why and when state reduction should be carried out, several results are obtained which describe the changes of the structure of a sequential machine under state reduction. It is seen that the undesirable effects of state reduction are closely associated with the failure of certain distributive laws to hold between the partitions used for state reduction and the partitions used in the realization of the unreduced machine.
ISSN:0019-9958
1878-2981
DOI:10.1016/S0019-9958(62)90588-0