On the Uniform Random Generation of Determinisitic Partially Ordered Automata using Monte Carlo Techniques

Pierre-Cyrille Héam (1, 2) , Jean-Luc Joly (1)

1 FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174)
2 CASSIS - Combination of approaches to the security of infinite states systems

Partially ordered automata are finite automata admitting no simple loops of length greater than or equal to 2. In this paper we show how to randomly and uniformly generate deterministic accessible partially ordered automata using Monte-Carlo techniques.

Domaines: Informatique et langage [cs.CL]

Pierre-Cyrille Héam, Jean-Luc Joly. On the Uniform Random Generation of Determinisitic Partially Ordered Automata using Monte Carlo Techniques. 2014. ⟨hal-01087751⟩