Asymptotic enumeration of minimal automata

DOI10.4230/LIPICS.STACS.2012.88MaRDI QIDQ2904752zbMATH OpenFDO

Authors Frédérique Bassino, Julien David, Andrea Sportiello

Publication date 23 August 2012

Full work available at URL https://arxiv.org/abs/1109.5683

zbMATH Keywords

minimal automataregular languagesenumeration of random structures

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We determine the asymptotic proportion of minimal automata, within n-state accessible deterministic complete automata over a k-letter alphabet, with the uniform distribution over the possible transition structures, and a binomial distribution over terminal states, with arbitrary parameter b. It turns out that a fraction ~ 1-C(k,b) n^{-k+2} of automata is minimal, with C(k,b) a function, explicitly determined, involving the solution of a transcendental equation.

Recommendations

• On the asymptotic enumeration of accessible automata
• Distribution of the number of accessible states in a random deterministic automaton
• Exact enumeration of acyclic deterministic automata
• Enumeration and random generation of accessible automata
• Random deterministic automata

Cited in

(12)

• On the asymptotic enumeration of accessible automata
• Sturmian and Infinitely Desubstitutable Words Accepted by an $$\omega $$-Automaton
• Compacted binary trees admit a stretched exponential
• Enumeration of minimal acyclic automata via generalized parking functions
• The minimal automaton recognizing \(m\mathbb N\) in a linear numeration system
• The state complexity of random DFAs
• scientific article; zbMATH DE number 3934415 (Why is no real title available?)
• scientific article; zbMATH DE number 777287 (Why is no real title available?)
• Counting Minimal Symmetric Difference NFAs
• Enumerating regular expressions and their languages
• Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language
• Random deterministic automata

This page was built for publication: Asymptotic enumeration of minimal automata

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