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
KEYWORD
nonn,tabf
AUTHOR
Jonathan Vos Post, Nov 01 2010
STATUS
approved