Carine Pivoteau ; Bruno Salvy ; Michèle Soria - Boltzmann Oracle for Combinatorial Systems

dmtcs:3585 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science - https://doi.org/10.46298/dmtcs.3585
Boltzmann Oracle for Combinatorial Systems

Authors: Carine Pivoteau 1; Bruno Salvy ORCID-iD2; Michèle Soria 1

  • 1 Algorithmes, Programmes et Résolution
  • 2 Algorithms

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 translate into numerical iteration schemes that provide such oracles. In particular, we give a fast oracle based on Newton iteration.


Volume: DMTCS Proceedings vol. AI, Fifth Colloquium on Mathematics and Computer Science
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: Random generation,Boltzmann generation,combinatorics,Newton iteration,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Funding:
    Source : HAL
  • Génération Aléatoire : Modèles, Méthodes et Algorithmes; Funder: French National Research Agency (ANR); Code: ANR-07-BLAN-0330

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV 0807.0992
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.0807.0992
  • 0807.0992
  • 10.48550/arxiv.0807.0992
Random XML sampling the Boltzmann way

4 Documents citing this article

Consultation statistics

This page has been seen 165 times.
This article's PDF has been downloaded 159 times.