Some Techniques of State Assignment for Synchronous Sequential Machines

Abstract

This paper is an extension of the work of Hartmanis and Stearns on sequential machine state assignments with reduced dependence. In Section II the critical partition pairs of transition-incomplete sequential machines are defined, and methods are given for computing them. Section III pursues certain combinatorial problems associated with the construction of assignments with reduced dependence, once the critical partition pairs are known. The algorithms derived in this paper provide the nucleus of a systematic procedure for the construction of economical state assignments.