login
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

%I #4 Feb 16 2020 20:49:49

%S 2,1,1,6,2,22,54,3,68,403,914,6,192,2228,10886,21874,9,512,9721,85974,

%T 360071,676326,18,1312,37736,526760,3809428,14229762,25392410

%N 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.

%C 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.

%H B. D. Johnson, J. P. Crutchfield, C. J. Ellison, C. S. McTague, <a href="http://arxiv.org/abs/1011.0036">Enumerating Finitary Processes</a>, Oct 30, 2010.

%e n=1, e=1, has 2 epsilon machines; n=1, e=2, has 1 epsilon machine.

%e n=2, e=2, has 1 epsilon machine; n=2, e=3, has 6 epsilon machines.

%e n=3, e=3, has 2 epsilon machine; n=3, e=4, has 22 epsilon machines;

%e n=3, e=5, has 54 epsilon machines.

%K nonn,tabf

%O 1,1

%A _Jonathan Vos Post_, Nov 01 2010