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,3

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

References

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.

Links

Table of n, a(n) for n=0..19.

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.

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.

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

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.

Sequence in context: A010040 A138379 A064815 * A368505 A296956 A366335

Adjacent sequences: A331117 A331118 A331119 * A331121 A331122 A331123

Keyword

nonn,changed

Author

Michael Wallner, Jan 10 2020

Status

approved