Random sampling from Boltzmann principles

Philippe Duchon; Philippe Flajolet; Guy Louchard; Gilles Schaeffer

doi:10.1007/3-540-45465-9_43

Random sampling from Boltzmann principles

Philippe Duchon
, Philippe Flajolet
, Guy Louchard
, Gilles Schaeffer

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This extended abstract proposes a surprisingly simple framework for the random generation of combinatorial configurations based on Boltzmann models. Random generation of possibly complex structured objects is performed by placingan appropriate measure spread over the whole of a combinatorial class. The resultingalg orithms can be implemented easily within a computer algebra system, be analysed mathematically with great precision, and, when suitably tuned, tend to be efficient in practice, as they often operate in linear time.

Original language	English
Title of host publication	Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings
Editors	Peter Widmayer, Stephan Eidenbenz, Francisco Triguero, Rafael Morales, Ricardo Conejo, Matthew Hennessy
Publisher	Springer Verlag
Pages	501-513
Number of pages	13
ISBN (Print)	3540438645, 9783540438649
DOIs	https://doi.org/10.1007/3-540-45465-9_43
Publication status	Published - 1 Jan 2002
Externally published	Yes
Event	29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 - Malaga, Spain Duration: 8 Jul 2002 → 13 Jul 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2380 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th International Colloquium on Automata, Languages, and Programming, ICALP 2002
Country/Territory	Spain
City	Malaga
Period	8/07/02 → 13/07/02

Access to Document

10.1007/3-540-45465-9_43

Cite this

Duchon, P., Flajolet, P., Louchard, G., & Schaeffer, G. (2002). Random sampling from Boltzmann principles. In P. Widmayer, S. Eidenbenz, F. Triguero, R. Morales, R. Conejo, & M. Hennessy (Eds.), Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings (pp. 501-513). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2380 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-45465-9_43

Duchon, Philippe ; Flajolet, Philippe ; Louchard, Guy et al. / Random sampling from Boltzmann principles. Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. editor / Peter Widmayer ; Stephan Eidenbenz ; Francisco Triguero ; Rafael Morales ; Ricardo Conejo ; Matthew Hennessy. Springer Verlag, 2002. pp. 501-513 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{abbdf6ea9caf424c950308e16373e565,

title = "Random sampling from Boltzmann principles",

abstract = "This extended abstract proposes a surprisingly simple framework for the random generation of combinatorial configurations based on Boltzmann models. Random generation of possibly complex structured objects is performed by placingan appropriate measure spread over the whole of a combinatorial class. The resultingalg orithms can be implemented easily within a computer algebra system, be analysed mathematically with great precision, and, when suitably tuned, tend to be efficient in practice, as they often operate in linear time.",

author = "Philippe Duchon and Philippe Flajolet and Guy Louchard and Gilles Schaeffer",

year = "2002",

month = jan,

day = "1",

doi = "10.1007/3-540-45465-9\_43",

language = "English",

isbn = "3540438645",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "501--513",

editor = "Peter Widmayer and Stephan Eidenbenz and Francisco Triguero and Rafael Morales and Ricardo Conejo and Matthew Hennessy",

booktitle = "Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings",

note = "29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 ; Conference date: 08-07-2002 Through 13-07-2002",

}

Duchon, P, Flajolet, P, Louchard, G & Schaeffer, G 2002, Random sampling from Boltzmann principles. in P Widmayer, S Eidenbenz, F Triguero, R Morales, R Conejo & M Hennessy (eds), Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2380 LNCS, Springer Verlag, pp. 501-513, 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002, Malaga, Spain, 8/07/02. https://doi.org/10.1007/3-540-45465-9_43

Random sampling from Boltzmann principles. / Duchon, Philippe; Flajolet, Philippe; Louchard, Guy et al.
Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. ed. / Peter Widmayer; Stephan Eidenbenz; Francisco Triguero; Rafael Morales; Ricardo Conejo; Matthew Hennessy. Springer Verlag, 2002. p. 501-513 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2380 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Random sampling from Boltzmann principles

AU - Duchon, Philippe

AU - Flajolet, Philippe

AU - Louchard, Guy

AU - Schaeffer, Gilles

PY - 2002/1/1

Y1 - 2002/1/1

N2 - This extended abstract proposes a surprisingly simple framework for the random generation of combinatorial configurations based on Boltzmann models. Random generation of possibly complex structured objects is performed by placingan appropriate measure spread over the whole of a combinatorial class. The resultingalg orithms can be implemented easily within a computer algebra system, be analysed mathematically with great precision, and, when suitably tuned, tend to be efficient in practice, as they often operate in linear time.

AB - This extended abstract proposes a surprisingly simple framework for the random generation of combinatorial configurations based on Boltzmann models. Random generation of possibly complex structured objects is performed by placingan appropriate measure spread over the whole of a combinatorial class. The resultingalg orithms can be implemented easily within a computer algebra system, be analysed mathematically with great precision, and, when suitably tuned, tend to be efficient in practice, as they often operate in linear time.

U2 - 10.1007/3-540-45465-9_43

DO - 10.1007/3-540-45465-9_43

M3 - Conference contribution

AN - SCOPUS:84869168747

SN - 3540438645

SN - 9783540438649

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 501

EP - 513

BT - Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings

A2 - Widmayer, Peter

A2 - Eidenbenz, Stephan

A2 - Triguero, Francisco

A2 - Morales, Rafael

A2 - Conejo, Ricardo

A2 - Hennessy, Matthew

PB - Springer Verlag

T2 - 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002

Y2 - 8 July 2002 through 13 July 2002

ER -

Duchon P, Flajolet P, Louchard G, Schaeffer G. Random sampling from Boltzmann principles. In Widmayer P, Eidenbenz S, Triguero F, Morales R, Conejo R, Hennessy M, editors, Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings. Springer Verlag. 2002. p. 501-513. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45465-9_43

Random sampling from Boltzmann principles

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this