Boltzmann Oracle for Combinatorial Systems

Conference object English OPEN
Pivoteau , Carine; Salvy , Bruno; Soria , Michèle;
  • Publisher: Discrete Mathematics & Theoretical Computer Science
  • Subject: [ MATH.MATH-CO ] Mathematics [math]/Combinatorics [math.CO] | [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] | Random generation | Newton iteration | [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] | [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS] | Boltzmann generation | combinatorics
    acm: TheoryofComputation_GENERAL

International audience; Boltzmann random generation applies to well-defined systems of recursive combinatorial equations. It relies on oracles giving values of the enumeration generating series inside their disk of convergence. We show that the combinatorial systems tran... View more
  • References (14)
    14 references, page 1 of 2

    [1] F. Bergeron, G. Labelle, and P. Leroux. Combinatorial species and tree-like structures, volume 67 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1998. ISBN 0-521-57323-8. Translated from the 1994 French original.

    [2] H. Cartan. Elementary theory of analytic functions of one or several complex variables. Dover Publications, 1995. ISBN 0486685438 (pbk.). URL description/dover031/95013507.html. Reprint of the 1973 ed, translated from the 1961 French original.

    [3] A. Darrasse. Random XML sampling the Boltzmann way. Technical Report 0807.0992, arXiv, 2008. URL

    [4] H. D´ecoste, G. Labelle, and P. Leroux. Une approche combinatoire pour l'it´eration de Newton-Raphson. Advances in Applied Mathematics, 3:407-416, 1982.

    [5] P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. Combinatorics, Probability and Computing, 13(4-5): 577-625, 2004. Special issue on Analysis of Algorithms.

    [6] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University Press, 2008. To be published, available from P. Flajolet's web page.

    [7] P. Flajolet, B. Salvy, and P. Zimmermann. Automatic average-case analysis of algorithms. Theoretical Computer Science Series A, 79(1):37-109, Feb. 1991.

    [8] P. Flajolet, E´. Fusy, and C. Pivoteau. Boltzmann sampling of unlabelled structures. In D. Applegate, G. S. Brodal, D. Panario, and R. Sedgewick, editors, Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics, volume 126 of SIAM Proceedings in Applied Mathematics, pages 201-211. SIAM, 2007. Workshops held in New Orleans, LA, January 2007.

    [9] A. Joyal. Une th´eorie combinatoire des s´eries formelles. Advances in Mathematics, 42(1): 1-82, 1981.

    [10] G. Labelle. E´closions combinatoires appliqu´ees `a l'inversion multidimensionnelle des s´eries formelles. Journal of Combinatorial Theory. Series A, 39(1):52-82, 1985. ISSN 0097-3165.

  • Metrics
    No metrics available
Share - Bookmark