Jean-Baptiste Priez - Enumeration of minimal acyclic automata via generalized parking functions

dmtcs:2471 - Discrete Mathematics & Theoretical Computer Science, January 1, 2015, DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015) - https://doi.org/10.46298/dmtcs.2471
Enumeration of minimal acyclic automata via generalized parking functionsConference paper

Authors: Jean-Baptiste Priez 1

  • 1 Laboratoire de Recherche en Informatique

[en]
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.

[fr]
On donne une formule d’énumération exacte des automates finites déterministes acycliques minimaux. Cetteformule s’obtient à partir d’une bijection entre une famille fonctions de parking généralisées et les fonctions detransitions des automates acycliques.

https://doi.org/10.46298/dmtcs.2471
Source: HAL:hal-01337781v1
Volume: DMTCS Proceedings, 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015)
Section: Proceedings
Published on: January 1, 2015
Imported on: November 21, 2016
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] minimal acyclic deterministic finite automata, finite language, generalized parking function, species
Licence: Attribution 4.0 International (CC BY 4.0)

2 Documents citing this article

Share and export

Consultation statistics

This page has been seen 354 times.
This article's PDF has been downloaded 499 times.