Random Sampling from Boltzmann principles

Philippe Duchon; Philippe Flajolet; Guy Louchard; Gilles Schaeffer

inria-00100938, version 1

Random Sampling from Boltzmann principles

Philippe Duchon^a^, 1, Philippe Flajolet ()^b^, 2, Guy Louchard^c^, 3, Gilles Schaeffer ()^d^, 4

29th International Colloquium on Automata, Languages and Programming - ICALP'2002 2380 (2002) 501-513

Abstract: This note proposes a new framework for random generation based on what we call Boltzmann models. The idea is to perform random generation of possibly complex structured objects by putting an appropriate measure on combinatorial classes. The resulting algorithms often operate in linear time. They can be easily implemented within a computer algebra system and will be theoretically as well as practically efficient.

a – LABRI
b – INRIA ROCQUENCOURT
c – UNIVERSITE LIBRE DE BRUXELLES
d – CNRS
1: Laboratoire Bordelais de Recherche en Informatique (LaBRI)
CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
2: SYDOCO (INRIA Rocquencourt)
INRIA
3: Université Libre de Bruxelles (ULB)
Université Libre de Bruxelles
4: ADAGE (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

inria-00100938, version 1
http://hal.inria.fr/inria-00100938
oai:hal.inria.fr:inria-00100938
From: Publications Loria <>
Submitted on: Tuesday, 26 September 2006 14:53:00
Updated on: Thursday, 28 September 2006 15:22:47

See detailed view

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="inproceedings"><head>Peer-reviewed conferences/proceedings</head>
<biblStruct type="inproceedings" xml:id="inria-00100938"><analytic>
<author><persName><forename>Philippe</forename><surname>Duchon</surname></persName>
<affiliation>
<orgName type="laboratory">LaBRI</orgName>
<orgName type="team">Laboratoire Bordelais de Recherche en Informatique</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5800</orgName>
<orgName type="institution">Université Sciences et Technologies - Bordeaux I</orgName>
<orgName type="institution">École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)</orgName>
<orgName type="institution">Université Victor Segalen - Bordeaux II</orgName>
</affiliation>
</author>
<author><persName><forename>Philippe</forename><surname>Flajolet</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">SYDOCO</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<author><persName><forename>Guy</forename><surname>Louchard</surname></persName>
<affiliation>
<orgName type="laboratory">ULB</orgName>
<orgName type="team">Université Libre de Bruxelles</orgName>
<country>BE</country>
<orgName type="institution">Université Libre de Bruxelles</orgName>
</affiliation>
</author>
<author><persName><forename>Gilles</forename><surname>Schaeffer</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">ADAGE</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">Random Sampling from Boltzmann principles</title></analytic><monogr><meeting>29th International Colloquium on Automata, Languages and Programming - ICALP'2002</meeting><imprint><publisher>Springer</publisher><pubPlace><settlement>Malaga</settlement><country> Spain</country></pubPlace><biblScope type="publicationDate">2002-11-00</biblScope><biblScope type="vol">2380</biblScope><biblScope type="pp">501-513</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00100938</idno></biblStruct>
</listBibl>
</listBibl>