Asymptotic enumeration of Minimal Automata

Andrea Sportiello; Frederique Bassino; Julien David

Asymptotic enumeration of Minimal Automata

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1109.5683 v1 pith:VPDSJ4MY submitted 2011-09-26 cs.FL math.CO

Asymptotic enumeration of Minimal Automata

Frederique Bassino , Julien David , Andrea Sportiello This is my paper

classification cs.FL math.CO

keywords automataminimalasymptoticdistributionaccessiblealphabetarbitrarybinomial

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

read the original 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.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Space-Efficient Language Generation in the Limit
cs.DS 2026-06 unverdicted novelty 7.0

A poly(s,k)-space streaming algorithm achieves generation gap O(k^{2s-2}) for DFA languages with s states over k symbols and captures all strings of length at least 2s-1, with a near-matching lower bound via communica...