|
%I #54 Apr 18 2024 12:50:39
%S 1,1,6,60,900,18480,487560,15824880,612504240,27619664640,
%T 1425084870240,82937356685760,5381249970008640,385518151040336640,
%U 30248651895457718400,2581418447382311243520,238181756821410417488640,23637327769847150582661120,2511570244361817605178754560,284573826857792109743033564160
%N Number of non-isomorphic minimal deterministic finite automata with n transient states recognizing a finite binary language.
%C Using parking functions, Priez obtained an exact enumerative formula for the number of non-isomorphic minimal deterministic finite automata (MADFA) with n states recognizing a finite language over an alphabet of size k > 0 (Priez, 2015). An exact generation of MADFAs is given by Almeida et al. (2008). In that paper, exact enumerative formulae for the number of MADFA with n states for 1 < n < 6 and any alphabet size are also presented. - _Nelma Moreira_, Mar 08 2021
%D Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height, J. Combin. Theory Ser. A, 172:105177, 2020.
%H Marco Almeida, Nelma Moreira, and Rogério Reis, <a href="https://doi.org/10.1142/S0129054108005930">Exact Generation of Minimal Acyclic Deterministic Finite Automata</a>. Int. J. Found. Comput. Sci. 19(4): 751-765 (2008).
%H Manosij Ghosh Dastidar and Michael Wallner, <a href="https://arxiv.org/abs/2404.08415">Asymptotics of relaxed k-ary trees</a>, arXiv:2404.08415 [math.CO], 2024. See p. 1.6.
%H Michael Domaratzki, Derek Kisman, and Jeffrey Shallit, <a href="https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=a85b01e07f4502b4f4d1875fca1e4cf5764e1f7b">On the number of distinct languages accepted by finite automata with n states</a>, J. Autom. Lang. Combinat. (2002) Vol. 77 No. 4, 469-486. See Section 6, f'_2(n).
%H Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, and Michael Wallner, <a href="https://arxiv.org/abs/1703.10031">Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height</a>, arXiv:1703.10031 [math.CO], 2017.
%H Andrew Elvey Price, Wenjie Fang, and Michael Wallner, <a href="https://doi.org/10.4230/LIPIcs.AofA.2020.11">Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language</a>, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 11:1-11:13.
%H Jean-Baptiste Priez, <a href="https://hal.archives-ouvertes.fr/hal-01337781">Enumeration of minimal acyclic automata via generalized parking functions.</a> 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp. 697-708. hal-01337781.
%F a(n) = b(n,n), where the sequence b(n,m) = 2*b(n,m-1) + (m+1)*b(n-1,m) - m*b(n-2,m-1) for n >= m > 1, b(n,1) = b(n,0) + 2*b(n-1,1) for n >= 1, b(n,0) = 1 for n >= 0.
%F For any k > 0, m(k,n) with m(k,1)=1 and s(2*m^k-1,n) = Sum_{t=1..n} (binomial(n-1,t-1) * s(2*(m+t)^k-t-1,n-t) * m(k,t)) where s(x,n) enumerates x-parking functions (Priez, 2015). - _Nelma Moreira_, Mar 08 2021
%Y Cf. A059412 (minimal unary DFAs).
%Y A082161 (2^(n-1)*A082161(n)) is an upper bound; furthermore these are not necessarily minimal but acyclic binary DFAs without (!) accepting states.
%Y A288950 (2^(n-1)*A288950(n)) is a lower bound.
%K nonn
%O 0,3
%A _Michael Wallner_, Jan 10 2020
|
