Random deterministic automata
From MaRDI portal
Publication:2921998
DOI10.1007/978-3-662-44522-8_2zbMATH Open1425.68222OpenAlexW2217322393MaRDI QIDQ2921998FDOQ2921998
Authors: Cyril Nicaud 
Publication date: 14 October 2014
Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)
Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-01772890/file/mfcs14.pdf
Recommendations
- Distribution of the number of accessible states in a random deterministic automaton
- Average case analysis of Moore's state minimization algorithm
- Average case analysis of Brzozowski's algorithm
- On the average complexity of Brzozowski's algorithm for deterministic automata with a small number of final states
- Enumeration and random generation of possibly incomplete deterministic automata
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45) Analysis of algorithms (68W40)
Cites Work
- REGAL: A Library to Randomly and Exhaustively Generate Automata
- Title not available (Why is that?)
- Analytic combinatorics
- Title not available (Why is that?)
- Random graphs.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Experimental Evaluation of Classical Automata Constructions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The transitive closure of a random digraph
- Random generation of DFAs
- Asymptotic enumeration of minimal automata
- The state complexity of random DFAs
- Enumeration and random generation of accessible automata
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- A calculus for the random generation of labelled combinatorial structures
- Enumeration and generation with a string automata representation
- Uniform random generation of decomposable structures using floating-point arithmetic
- On the average complexity of Moore's state minimization algorithm
- Title not available (Why is that?)
- Brzozowski algorithm is generically super-polynomial for deterministic automata
- On the asymptotic enumeration of accessible automata
- An Asymptotic Formula for the Differences of the Powers at Zero
- Introducing VAUCANSON
- Average complexity of Moore's and Hopcroft's algorithms
- Average case analysis of Moore's state minimization algorithm
- Distribution of the number of accessible states in a random deterministic automaton
- A Census of Finite Automata
- A fast algorithm finding the shortest reset words
- On the average complexity of Brzozowski's algorithm for deterministic automata with a small number of final states
Cited In (14)
- Brzozowski algorithm is generically super-polynomial for deterministic automata
- On the uniform random generation of non deterministic automata up to isomorphism
- Synchronizing almost-group automata
- Asymptotic enumeration of minimal automata
- Distribution of the number of accessible states in a random deterministic automaton
- Automata recognizing no words: a statistical approach
- Random generation and enumeration of accessible deterministic real-time pushdown automata
- Title not available (Why is that?)
- Diameter and stationary distribution of random \(r\)-out digraphs
- Finitely nonstationary nondeterministic automata with random input
- Random generation of DFAs
- The graph structure of a deterministic automaton chosen at random
- On the uniform distribution of regular expressions
- Non-deterministic Weighted Automata on Random Words
This page was built for publication: Random deterministic automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921998)
