Enumeration and random generation of accessible automata
From MaRDI portal
Publication:995562
DOI10.1016/j.tcs.2007.04.001zbMath1188.68168OpenAlexW2013433986MaRDI QIDQ995562
Cyril Nicaud, Frédérique Bassino
Publication date: 3 September 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.001
Related Items (23)
The state complexity of random DFAs ⋮ Random Deterministic Automata ⋮ Generating, sampling and counting subclasses of regular tree languages ⋮ On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism ⋮ Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata ⋮ Empirical studies in the size of diagnosers and verifiers for diagnosability analysis ⋮ REGAL: A Library to Randomly and Exhaustively Generate Automata ⋮ Average case analysis of Moore's state minimization algorithm ⋮ Sampling different kinds of acyclic automata using Markov chains ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ Parametric random generation of deterministic tree automata ⋮ Succinct representations for (non)deterministic finite automata ⋮ A large deviations principle for the Maki-Thompson rumour model ⋮ Enumeration and generation with a string automata representation ⋮ On the average state and transition complexity of finite languages ⋮ Compacted binary trees admit a stretched exponential ⋮ Random Generation of Deterministic Acyclic Automata Using Markov Chains ⋮ Random Generation of Deterministic Tree (Walking) Automata ⋮ Semicomputable points in Euclidean spaces ⋮ Average complexity of Moore's and Hopcroft's algorithms ⋮ Enumerating regular expressions and their languages ⋮ Diagnosability verification using LTL model checking ⋮ Succinct representation for (non)deterministic finite automata
Cites Work
- A method and two algorithms on the theory of partitions
- Uniform random generation of decomposable structures using floating-point arithmetic
- The state complexities of some basic operations on regular languages
- A calculus for the random generation of labelled combinatorial structures
- Random generation of DFAs
- On the Lambert \(w\) function
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Boltzmann Sampling of Unlabelled Structures
- Enumeration of strongly connected sequential machines
- A Census of Finite Automata
- An Asymptotic Formula for the Differences of the Powers at Zero
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Enumeration and random generation of accessible automata
