10.4230/LIPICS.STACS.2012.194
Carayol, Arnaud
Arnaud
Carayol
Nicaud, Cyril
Cyril
Nicaud
Distribution of the number of accessible states in a random deterministic automaton
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2012
Article
finite automata
random sampling
average complexity
Dürr, Christoph
Christoph
Dürr
Wilke, Thomas
Thomas
Wilke
2012
2012-02-24
2012-02-24
2012-02-24
en
urn:nbn:de:0030-drops-34422
10.4230/LIPIcs.STACS.2012
978-3-939897-35-4
1868-8969
10.4230/LIPIcs.STACS.2012
LIPIcs, Volume 14, STACS 2012
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
2013
14
19
194
205
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Dürr, Christoph
Christoph
Dürr
Wilke, Thomas
Thomas
Wilke
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2012
14
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
802923 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
We study the distribution of the number of accessible states in deterministic and complete automata with n states over a k-letters alphabet. We show that as n tends to infinity and for a fixed alphabet size, the distribution converges in law toward a Gaussian centered around vk n and of standard deviation equivalent to sk n^(1/2), for some explicit constants vk and sk. Using this characterization, we give a simple algorithm for random uniform generation of accessible deterministic and complete automata of size n of expected complexity O(n^(3/2)), which matches the best methods known so far. Moreover, if we allow a variation around n in the size of the output automaton, our algorithm is the first solution of linear expected complexity. Finally we show how this work can be used to study accessible automata (which are difficult to apprehend from a combinatorial point of view) through the prism of the simpler deterministic and complete automata. As an example, we show how the average complexity in O(n log log n) for Moore's minimization algorithm obtained by David for deterministic and complete automata can be extended to accessible automata.
LIPIcs, Vol. 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012), pages 194-205