Have a personal or library account? Click to login

Pointed versus singular Boltzmann samplers: a comparative analysis

Pure Mathematics and Applications
Volume 25 (2015): Issue 2 (December 2015)
By:
Open Access
|Jun 2016

References

  1. [1] A. Bacher, O. Bodini and A. Jacquot, Efficient random sampling of binary and unarybinary trees via holonomic equations, at http://arxiv.org/abs/1401.1140.
    Search in Google Scholar
  2. [2] A. Bacher, O. Bodini and A. Jacquot, Exact-size sampling for Motzkin trees in linear time via Boltzmann samplers and holonomic specification, in: M. Nebel and W. Szpankowski (Eds.), Prooceedings of the 10th Workshop on Analytic Algorithmics and Combinatorics (ANALCO), SIAM Press ed., (2013) 52-61.
    Search in Google Scholar
  3. [3] F. Bassino and C. Nicaud, Enumeration and random generation of accessible automata, Theoret. Comput. Sci., 381 (2007) 86-104.
    Search in Google Scholar
  4. [4] F. Bassino, C. Nicaud and P. Weil, Random generation of finitely generated subgroups of a free group, Internat. J. Algebra Comput., 18 (2008) 375-405.
    Search in Google Scholar
  5. [5] O. Bodini, É. Fusy and C. Pivoteau, Random sampling of plane partitions, Combin. Probab. Comput., 19 (2010) 201-226.
    Search in Google Scholar
  6. [6] O. Bodini, J. Lumbroso and N. Rolin, Analytic samplers and the combinatorial rejection method, in: R. Sedgewick and M. D.Ward (Eds.), Proceedings of the 12thWorkshop on Analytic Algorithmics and Combinatorics (ANALCO), (2015) 40-50.
    Search in Google Scholar
  7. [7] O. Bodini and Y. Ponty, Multi-dimensional Boltzmann sampling of languages, Discrete Math. Theor. Comput. Sci. Proc., 1 (2010) 49-64.10.46298/dmtcs.2793
    Search in Google Scholar
  8. [8] O. Bodini, O. Roussel and M. Soria, Boltzmann samplers for first-order differential specifications, Discrete Appl. Math., 160 (2012) 2563-2572.10.1016/j.dam.2012.05.022
    Search in Google Scholar
  9. [9] B. Canou and A. Darrasse, Fast and sound random generation for automated testing and benchmarking in objective caml, in: Proceedings of the 2009 ACM SIGPLAN Workshop on ML, ACM New York (2009), 61-70.10.1145/1596627.1596637
    Search in Google Scholar
  10. [10] P. Duchon, Random generation of combinatorial structures: Boltzmann samplers and beyond, in: S. Jain, R. R. Creasey, J. Himmelspach, K. P. White and M. Fu (Eds.), Proceedings of Winter Simulation Conference (2011), 120-132.10.1109/WSC.2011.6147745
    Search in Google Scholar
  11. [11] P. Duchon, P. Flajolet, G. Louchard and G. Schaeffer, Boltzmann samplers for the random generation of combinatorial structures, Combin. Probab. Comput., 13 (2004) 577-625.
    Search in Google Scholar
  12. [12] P. Flajolet, É. Fusy and C. Pivoteau, Boltzmann sampling of unlabeled structures, in: D. Panario and R. Sedgewick (Eds.), Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), SIAM Press ed., (2007), 201-211.
    Search in Google Scholar
  13. [13] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.10.1017/CBO9780511801655
    Search in Google Scholar
  14. [14] P. Flajolet, P. Zimmermann and B. Van Cutsem, A calculus for the random generation of labelled combinatorial structures, Theoret. Comput. Sci., 132 (1994) 1-35.
    Search in Google Scholar
  15. [15] A. Nijenhuis and H. S. Wilf, Combinatorial algorithms for computers and calculators. Computer science and applied mathematics, Academic Press, New York, 1978.
    Search in Google Scholar
  16. [16] C. Pivoteau, B. Salvy and M. Soria, Algorithms for combinatorial structures: well-founded systems and Newton iterations, J. Combin. Theory Ser. A, 119 (2012) 1711-1773. 10.1016/j.jcta.2012.05.007
    Search in Google Scholar
  17. [17] J. L. Rémy, Un procédé itératif de dénombrement d’arbres binaires et son application a leur génération aléatoire, RAIRO Theor. Inform. Appl., 19 (1985) 179-195.
    Search in Google Scholar
DOI: https://doi.org/10.1515/puma-2015-0012 | Journal eISSN: 1788-800X
Journal RSS Feed
Language: English
Page range: 115 - 131
Submitted on: Oct 10, 2014
Published on: Jun 24, 2016
Published by: Corvinus University of Budapest
In partnership with: Paradigm Publishing Services
Publication frequency: 4 issues per year
Keywords:
Boltzmann sampler,
analysis of algorithms,
analytic combinatorics
Related subjects:
Computer sciences,
Theoretical computer sciences,
Business and economics,
Mathematics and statistics for economists,
Mathematics,
Mathematics,
Analysis,
Differential equations and dynamical systems

© 2016 Olivier Bodini, Antoine Genitrini, Nicolas Rolin, published by Corvinus University of Budapest
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 25 (2015): Issue 2 (December 2015)Next article