A Census of Finite Automata
- 1 January 1965
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 17, 100-113
- https://doi.org/10.4153/cjm-1965-010-9
Abstract
A finite automaton may be thought of as a possible abstraction of a digital computer. Imagine a tape or sequence of letters from some alphabet being fed into a device with a finite number of internal states. When the device is in a particular state and receives an input letter, the system passes to another internal state and prints a letter on an output tape. This operation is continued until the entire input sequence has been processed.Both Harary (6) and Ginsburg (4) have focused attention on the previously unsolved problem of counting the number of equivalence classes of finite automata. In the present paper, this problem is solved completely by proving a variety of theorems about the enumeration of functions.Keywords
This publication has 4 references indexed in Scilit:
- On the number of bi-colored graphsPacific Journal of Mathematics, 1958
- The number of linear, directed, rooted, and connected graphsTransactions of the American Mathematical Society, 1955
- The number of structures of finite relationsProceedings of the American Mathematical Society, 1953
- Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische VerbindungenActa Mathematica, 1937