Distribution of the number of accessible states in a random deterministic automaton

Authors Arnaud Carayol, Cyril Nicaud



PDF
Thumbnail PDF

File

LIPIcs.STACS.2012.194.pdf
  • Filesize: 0.76 MB
  • 12 pages

Document Identifiers

Author Details

Arnaud Carayol
Cyril Nicaud

Cite AsGet BibTex

Arnaud Carayol and Cyril Nicaud. Distribution of the number of accessible states in a random deterministic automaton. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 194-205, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.STACS.2012.194

Abstract

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.
Keywords
  • finite automata
  • random sampling
  • average complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail