Enumeration of minimal acyclic automata via generalized parking functions

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.

Keywords

• generalized parking function
• species
• finite language
• minimal acyclic deterministic finite automata
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]