Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

DOI10.4230/LIPICS.AOFA.2020.11MaRDI QIDQ5874410zbMATH OpenOpenAlexFDO

Authors W. Fang, Michael Wallner

Publication date 7 February 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/12041/pdf/LIPIcs-AofA-2020-11.pdf/

zbMATH Keywords

Airy functionasymptoticsbijectioncompacted treesdirected acyclic graphsDyck pathsfinite languagesminimal automatastretched exponential

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Recommendations

• Asymptotic enumeration of minimal automata
• Bideterministic automata and minimal representations of regular languages
• Bideterministic Automata and Minimal Representations of Regular Languages
• scientific article; zbMATH DE number 3273201
• The minimization of a kind of non-deterministic finite automata
• scientific article; zbMATH DE number 4108165
• scientific article; zbMATH DE number 4166871
• scientific article; zbMATH DE number 4108164
• On the determinization blowup for finite automata recognizing equal-length languages
• scientific article; zbMATH DE number 3390659

Cited in

(6)

• Compacted binary trees admit a stretched exponential
• Bideterministic Automata and Minimal Representations of Regular Languages
• scientific article; zbMATH DE number 1948499 (Why is no real title available?)
• Enumerative and distributional results for d-combining tree-child networks
• Asymptotic analysis and efficient random sampling of directed ordered acyclic graphs
• Asymptotics of relaxed k-ary trees

This page was built for publication: Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874410)