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