
Accession Number : AD0717291
Title : On the Enumeration of Finite State Synchronous Sequential Machines.
Descriptive Note : Interim technical rept.,
Corporate Author : UNIVERSITY OF SOUTHERN CALIFORNIA LOS ANGELES DEPT OF ELECTRICAL ENGINEERING
Personal Author(s) : Bottlik,Ivan Pal
Report Date : JUN 1970
Pagination or Media Count : 196
Abstract : The finite state synchronous sequential machine is a model of a digital computer or logical circuit. If, in an arbitrary system, one machine (i.e. finite state synchronous sequential machine) can be replaced by another machine without affecting the performance of the system then the machines are said to be the same (equivalent). The replacement may be carried out under a variety of restrictions. Fundamental relationships among the various types of equivalences are derived. It is also proven that every group machine is a disjoint aggregate of strongly connected group machines. Enumeration formulas are obtained and proven for: (1) the number of permutationally inequivalent machines having k internal states, n input states, and m output states; (2) the number of permutationally inequivalent group machines having k internal states, n input states, and m output states; and (3) the number of functionally inequivalent strongly connected group machines having no more than k states, one input state, and two output states. Enumeration formulas for the number of nonisomorphic machines, group machines having k internal states, n input states, and m output states follow directly from the formulas (1) and (2) respectively. (Author)
Descriptors : (*DIGITAL COMPUTERS, MATHEMATICAL MODELS), (*LOGIC CIRCUITS, COMBINATORIAL ANALYSIS), SWITCHING CIRCUITS, GROUPS(MATHEMATICS), SET THEORY, COMPUTER LOGIC, THEOREMS, THESES
Subject Categories : Computer Hardware
Distribution Statement : APPROVED FOR PUBLIC RELEASE