Accessible and Deterministic Automata: Enumeration and Boltzmann Samplers
| Autor: | Frédérique Bassino, Cyril Nicaud |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2006 |
| Předmět: |
finite automata
bijection asymptotic enumeration random generation boltzmann samplers [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] Mathematics QA1-939 |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AG,..., Iss Proceedings (2006) |
| Druh dokumentu: | article |
| ISSN: | 1365-8050 |
| DOI: | 10.46298/dmtcs.3499 |
| Popis: | We present a bijection between the set $\mathcal{A}_n$ of deterministic and accessible automata with $n$ states on a $k$-letters alphabet and some diagrams, which can themselves be represented as partitions of the set $[\![ 1..(kn+1) ]\!]$ into $n$ non-empty parts. This combinatorial construction shows that the asymptotic order of the cardinality of $\mathcal{A}_n$ is related to the Stirling number $\{^{kn}_n\}$. Our bijective approach also yields an efficient random sampler of automata with $n$ states, of complexity $O(n^{3/2})$, using the framework of Boltzmann samplers. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|