2026-07-23T05:31:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12041 2024-03-06T10:49:15Z ddc:004 open_access

Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language Elvey Price, Andrew Fang, Wenjie Wallner, Michael Airy function asymptotics directed acyclic graphs Dyck paths bijection stretched exponential compacted trees minimal automata finite languages 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrew Elvey Price and Wenjie Fang and Michael Wallner 2020 Is Part Of LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2020.11 urn:nbn:de:0030-drops-120419 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.11 eng https://creativecommons.org/licenses/by/3.0/legalcode