login
A181621
Table by rows, the number E(n;2) of binary-alphabet topological epsilon-machines as a function of the number of states n and edges k.
1
2, 1, 1, 6, 2, 22, 54, 3, 68, 403, 914, 6, 192, 2228, 10886, 21874, 9, 512, 9721, 85974, 360071, 676326, 18, 1312, 37736, 526760, 3809428, 14229762, 25392410
OFFSET
1,1
COMMENTS
From Table 1, p. 6 of Johnson. Abstract: We show how to efficiently enumerate a class of finite-memory stochastic processes using the causal representation of epsilon-machines. We characterize epsilon-machines in the language of automata theory and adapt a recent algorithm for generating accessible deterministic finite automata, pruning this over-large class down to that of epsilon-machines. As an application, we exactly enumerate topological epsilon-machines up to seven states and six-letter alphabets.
LINKS
B. D. Johnson, J. P. Crutchfield, C. J. Ellison, C. S. McTague, Enumerating Finitary Processes, Oct 30, 2010.
EXAMPLE
n=1, e=1, has 2 epsilon machines; n=1, e=2, has 1 epsilon machine.
n=2, e=2, has 1 epsilon machine; n=2, e=3, has 6 epsilon machines.
n=3, e=3, has 2 epsilon machine; n=3, e=4, has 22 epsilon machines;
n=3, e=5, has 54 epsilon machines.
CROSSREFS
Sequence in context: A112477 A372973 A156984 * A307070 A084268 A332405
KEYWORD
nonn,tabf
AUTHOR
Jonathan Vos Post, Nov 01 2010
STATUS
approved