[Back]

M. Wallner, A. Price, W. Fang:
"Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language";
Talk: AofA 2020, Klagenfurt; 2020-06-15 - 2020-06-20; in: "31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)", M. Drmota, C. Heuberger (ed.); Leibniz International Proceedings in Informatics (LIPIcs), 159 (2020), ISBN: 978-3-95977-147-4; 1 - 13.

We show that the number of minimal deterministic finite automata with n+1 states recognizing a finite binary language grows asymptotically for n → ∞ like Θ(n! 8ⁿ e^{3 a₁ n^{1/3}} n^{7/8}), where a₁ ≈ -2.338 is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two-parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Netwon polygons.

http://dx.doi.org/10.4230/LIPIcs.AofA.2020.11