Enumeration of minimal acyclic automata via generalized parking functions

MaRDI QIDQ2803338zbMATH OpenFDO

Authors Jean-Baptiste Priez

Publication date 4 May 2016

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

zbMATH Keywords

finite languagegeneralized parking functionminimal acyclic deterministic finite automataspecies

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Formal languages and automata (68Q45)

Abstract: We give an exact enumerative formula for the minimal acyclic deterministic finite automata. This formula is obtained from a bijection between a family of generalized parking functions and the transitions functions of acyclic automata.

Recommendations

• Exact enumeration of acyclic deterministic automata
• Asymptotic enumeration of minimal automata
• EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA
• On the asymptotic enumeration of accessible automata
• Minimisation of acyclic deterministic automata in linear time

Cited in

(2)

• Exact enumeration of acyclic deterministic automata
• A determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata

This page was built for publication: Enumeration of minimal acyclic automata via generalized parking functions

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