CLASSIFICATION AND ENUMERATION OF AUTONOMOUS SEQUENTIAL MACHINES.
ILLINOIS UNIV AT URBANA ENGINEERING EXPERIMENT STATION
Pagination or Media Count:
A study is reported of the structure of the state transition graphs of autonomous sequential machines. An autonomous sequential machine can be viewed as an isolated, discrete information processing system. The structural properties of the graphs are formally described. A state transition graph is proved to have a unique partitioning into components. It is also proved that a component has a canonical partition into functional rooted trees, and a functional rooted tree can be decomposed into a forest of functional rooted trees. Using the structural properties of the state transition graphs, nested classification systems are defined for the set of autonomous sequential machines having labeled states and for the set of autonomous sequential machines having unlabeled states. All the enumeration problems associated with the classification systems are solved. Expressions are given for the number of connected labeled machines and the number of connected unlabeled machines. Solutions are also given for several counting problems of more general application. Recursive formulas were found for counting labeled and unlabeled rooted trees. The problem of finding the number of cyclic permutations with non-distinct elements is solved a formula for calculating the coefficients of the Bell polynomials is given. Numerical results are tabulated for autonomous sequential machines having from one to five states. Author