login
Array read by antidiagonals: the number of automata over an n-letter alphabet whose states are determined by the last k symbols read.
1

%I #35 Aug 04 2020 06:18:45

%S 1,1,2,1,5,5,1,30,192,15,1,1247

%N Array read by antidiagonals: the number of automata over an n-letter alphabet whose states are determined by the last k symbols read.

%C T(n,k) is the number of automata over an n-letter alphabet whose states are determined by the last k symbols read. These therefore correspond to a count of a special class of synchronized automata as in the Road Coloring Problem solved by Trahtman.

%C Also, T(n,k) counts equivalence relations on de Bruijn graphs compatible with edge labels.

%H Collin Bleak, <a href="/A248905/a248905.txt">Table of a(n,k) listed as antidiagonal ordered sequence in index m = 1..15.</a>

%H Collin Bleak, Peter J. Cameron, and Feyishayo Olukoya, <a href="https://arxiv.org/abs/2004.08478">Automorphisms of shift spaces and the Higman-Thomspon groups: the one-sided case</a>, arXiv:2004.08478 [math.GR], 2020.

%H Avraham N. Trahtman, <a href="http://arxiv.org/abs/0709.0099">The Road Coloring Problem</a>, arXiv:0709.0099 [cs.DM], 2007.

%H Avraham N. Trahtman, <a href="http://dx.doi.org/10.1007/s11856-009-0062-5">The Road Coloring Problem</a>, Israel Journal of Mathematics, 172 (2009), 51-60.

%F T(n,1) = A000110(n).

%e Below is the table T(n,k) for row n = alphabet size, and column k = synchronizing word length. Top left entry is T(1,1).

%e 1 1 1 1 1 1 ...

%e 2 5 30 1247 ?

%e 5 192 ? ?

%e 15 98721 ?

%e 203 ?

%e .

%e .

%e .

%Y Cf. A000110 (first column).

%K hard,more,nonn,tabl

%O 1,3

%A _Collin Bleak_ and _Peter J. Cameron_, Mar 06 2015