On the Enumeration of Finite State Synchronous Sequential Machines.

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