A331120 Number of non-isomorphic minimal deterministic finite automata with n transient states recognizing a finite binary language.

1, 1, 6, 60, 900, 18480, 487560, 15824880, 612504240, 27619664640, 1425084870240, 82937356685760, 5381249970008640, 385518151040336640, 30248651895457718400, 2581418447382311243520, 238181756821410417488640, 23637327769847150582661120, 2511570244361817605178754560, 284573826857792109743033564160

Offset: 0

Author

Michael Wallner, Jan 10 2020

Keywords

• nonn

Comments

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

Links

• Marco Almeida, Nelma Moreira, and Rogério Reis, Exact Generation of Minimal Acyclic Deterministic Finite Automata. Int. J. Found. Comput. Sci. 19(4): 751-765 (2008).
• Manosij Ghosh Dastidar and Michael Wallner, Asymptotics of relaxed k-ary trees, arXiv:2404.08415 [math.CO], 2024. See p. 1.6.
• Michael Domaratzki, Derek Kisman, and Jeffrey Shallit, On the number of distinct languages accepted by finite automata with n states, J. Autom. Lang. Combinat. (2002) Vol. 77 No. 4, 469-486. See Section 6, f'_2(n).
• Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, and Michael Wallner, Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height, arXiv:1703.10031 [math.CO], 2017.
• 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.
• Andrew Elvey Price, Wenjie Fang, and Michael Wallner, Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language, 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.
• Jean-Baptiste Priez, Enumeration of minimal acyclic automata via generalized parking functions. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. pp. 697-708. hal-01337781.

Crossrefs

Cf. A059412 (minimal unary DFAs).

A082161 (2^(n-1)*A082161(n)) is an upper bound; furthermore these are not necessarily minimal but acyclic binary DFAs without (!) accepting states.

A288950 (2^(n-1)*A288950(n)) is a lower bound.

Formula

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.

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