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.

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

Table of n, a(n) for n=1..29.

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: A085826 A112477 A156984 * A307070 A084268 A332405

Adjacent sequences: A181618 A181619 A181620 * A181622 A181623 A181624

Keyword

nonn,tabf

Author

Jonathan Vos Post, Nov 01 2010

Status

approved