On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism
DOI10.1007/978-3-319-22360-5_12zbMath1465.68146arXiv1512.02797OpenAlexW3099640518MaRDI QIDQ2947416
Jean-Luc Joly, Pierre-Cyrille Héam
Publication date: 23 September 2015
Published in: Implementation and Application of Automata (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1512.02797
Computational methods in Markov chains (60J22) Formal languages and automata (68Q45) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Sampling different kinds of acyclic automata using Markov chains
- Enumeration and random generation of accessible automata
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- A note on the graph isomorphism counting problem
- A dynamic survey of graph labeling
- Random generation of DFAs
- Enumeration and generation with a string automata representation
- Random Deterministic Automata
- On the Average Size of Glushkov’s Automata
- Isomorphism Testing for Graphs, Semigroups, and Finite Automata are Polynomially Equivalent Problems
- Random Generation of Deterministic Acyclic Automata Using Markov Chains
- Experimental Evaluation of Classical Automata Constructions
- Probability and Computing
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism
