Document Open Access Logo

Uniform Sampling for Networks of Automata

Authors Nicolas Basset, Jean Mairesse, Michèle Soria

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2017.36.pdf
  • Filesize: 0.59 MB
  • 16 pages

Document Identifiers

Author Details

Nicolas Basset
Jean Mairesse
Michèle Soria

Cite AsGet BibTex

Nicolas Basset, Jean Mairesse, and Michèle Soria. Uniform Sampling for Networks of Automata. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CONCUR.2017.36

Abstract

We call network of automata a family of partially synchronised automata, i.e. a family of deterministic automata which are synchronised via shared letters, and evolve independently otherwise. We address the problem of uniform random sampling of words recognised by a network of automata. To that purpose, we define the reduced automaton of the model, which involves only the product of the synchronised part of the component automata. We provide uniform sampling algorithms which are polynomial with respect to the size of the reduced automaton, greatly improving on the best known algorithms. Our sampling algorithms rely on combinatorial and probabilistic methods and are of three different types: exact, Boltzmann and Parry sampling.
Keywords
  • Partially synchronised automata
  • uniform sampling; recursive method
  • Boltzmann sampling
  • Parry measure

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Samy Abbes and Jean Mairesse. Uniform generation in trace monoids. In G. Italiano, G. Pighizzini, and D. Sannella, editors, Math. Found. Comput. Sc. 2015 (MFCS 2015), part 1, volume 9234 of Lecture Notes in Comput. Sci., pages 63-75. Springer, 2015. Google Scholar
  2. Alfred Aho, Rajeev Motwani, and Jeffrey Ullman. Introduction to Automata Theory, Languages, and Computation: 2nd edition. Addison Wesley, 2001. Google Scholar
  3. Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008. Google Scholar
  4. Nicolas Basset, Michèle Soria, and Jean Mairesse. Uniform sampling for networks of automata, 2017. URL: http://hal.upmc.fr/hal-01545936.
  5. Olivier Bernardi and Omer Giménez. A linear algorithm for the random sampling from regular languages. Algorithmica, 62(1-2):130-145, 2012. Google Scholar
  6. Jean Berstel and Christophe Reutenauer. Noncommutative rational series with applications, volume 137 of Enc. of Math. and Appl. Cambridge University Press, 2011. Google Scholar
  7. Olivier Bodini, Antoine Genitrini, and Frédéric Peschanski. The combinatorics of non-determinism. In Anil Seth and Nisheeth K. Vishnoi, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2013, December 12-14, 2013, Guwahati, India, volume 24 of LIPIcs, pages 425-436. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2013.425.
  8. Alexis Darrasse, Konstantinos Panagiotou, Olivier Roussel, and Michele Soria. Biased Boltzmann samplers and generation of extended linear languages with shuffle. DMTCS Proceedings, 01:125-140, 2012. Google Scholar
  9. Alain Denise, Marie-Claude Gaudel, Sandrine-Dominique Gouraud, Richard Lassaigne, Johan Oudinet, and Sylvain Peyronnet. Coverage-biased random exploration of large models and application to testing. STTT, 14(1):73-93, 2012. URL: http://dx.doi.org/10.1007/s10009-011-0190-1.
  10. Philippe Duchon, Philippe Flajolet, Guy Louchard, and Gilles Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. Combinatorics, Probability and Computing, 13(4-5):577-625, 2004. Google Scholar
  11. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, New York, NY, USA, 1 edition, 2009. Google Scholar
  12. Philippe Flajolet, Paul Zimmerman, and Bernard Van Cutsem. A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science, 132(1):1-35, 1994. Google Scholar
  13. Radu Grosu and Scott A. Smolka. Monte carlo model checking. In TACAS'05, 2005. Google Scholar
  14. Dexter Kozen. Lower bounds for natural proof systems. In FOCS, volume 77, pages 254-266, 1977. Google Scholar
  15. M. Lothaire. Applied Combinatorics on Words (Encyclopedia of Mathematics and its Applications). Cambridge University Press, New York, NY, USA, 2005. Google Scholar
  16. Kuldeep S. Meel, Moshe Y. Vardi, Supratik Chakraborty, Daniel J. Fremont, Sanjit A. Seshia, Dror Fried, Alexander Ivrii, and Sharad Malik. Constrained sampling and counting: Universal hashing meets SAT solving. In Adnan Darwiche, editor, Beyond NP, Papers from the 2016 AAAI Workshop, Phoenix, Arizona, USA, February 12, 2016., volume WS-16-05 of AAAI Workshops. AAAI Press, 2016. URL: http://www.aaai.org/ocs/index.php/WS/AAAIW16/paper/view/12618.
  17. Mehryar Mohri. Generic ε-removal algorithm for weighted automata. In International Conference on Implementation and Application of Automata, pages 230-242. Springer, 2000. Google Scholar
  18. Madhavan Mukund. Automata on distributed alphabets. In Modern Applications of Automata Theory, pages 257-288. World Scientific, 2012. URL: http://dx.doi.org/10.1142/9789814271059_0009.
  19. Johan Oudinet, Alain Denise, and Marie-Claude Gaudel. A new dichotomic algorithm for the uniform random generation of words in regular languages. Theor. Comput. Sci., 502:165-176, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.07.025.
  20. Johan Oudinet, Alain Denise, Marie-Claude Gaudel, Richard Lassaigne, and Sylvain Peyronnet. Uniform monte-carlo model checking. In FASE 2011, pages 127-140, 2011. Google Scholar
  21. Antonio Restivo. The shuffle product: New research directions. In International Conference on Language and Automata Theory and Applications, pages 70-81. Springer, 2015. Google Scholar
  22. A. Salomaa and M. Soittola. Automata-theoretic aspects of formal power series. Springer Verlag, 1978. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact