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 non-isomorphic 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