Alexis Darrasse ; Konstantinos Panagiotou ; Olivier Roussel ; Michele Soria - Biased Boltzmann samplers and generation of extended linear languages with shuffle

dmtcs:2989 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) - https://doi.org/10.46298/dmtcs.2989
Biased Boltzmann samplers and generation of extended linear languages with shuffle

Authors: Alexis Darrasse ; Konstantinos Panagiotou ; Olivier Roussel ; Michele Soria

    This paper is devoted to the construction of Boltzmann samplers according to various distributions, and uses stochastic bias on the parameter of a Boltzmann sampler, to produce a sampler with a different distribution for the size of the output. As a significant application, we produce Boltzmann samplers for words defined by regular specifications containing shuffle operators and linear recursions. This sampler has linear complexity in the size of the output, where the complexity is measured in terms of real-arithmetic operations and evaluations of generating functions.


    Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
    Section: Proceedings
    Published on: January 1, 2012
    Imported on: January 31, 2017
    Keywords: Boltzmann samplers,biased distributions,shuffle operator,combinatorial specifications,generating functions,random sampling,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

    1 Document citing this article

    Share

    Consultation statistics

    This page has been seen 141 times.
    This article's PDF has been downloaded 124 times.