Random Generation of Deterministic Acyclic Automata Using the Recursive Method

Overview & Synopsis

In this article, we propose a uniform random generator for accessible deterministic acyclic automata with n states, which is based on the recursive method. The generator has a preprocessing that requires O(n3) arithmetic operations, and, once it is done, can generate acyclic automata using O(n) arithmetic operations for each sample. We also propose a lazy version of the algorithm that takes advantage of the typical shape of random acyclic automata to reduce experimentally the preprocessing. Using this algorithm, we provide some statistics on acyclic automata with up to 1000 states.