Biased Boltzmann samplers and generation of extended linear languages with shuffle - Archive ouverte HAL Access content directly
Conference Papers Discrete Mathematics and Theoretical Computer Science Year : 2012

Biased Boltzmann samplers and generation of extended linear languages with shuffle

(1) , (2) , (1) , (1)
1
2

Abstract

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.
Fichier principal
Vignette du fichier
dmAQ0111.pdf (362.92 Ko) Télécharger le fichier
Origin : Publisher files allowed on an open archive
Loading...

Dates and versions

hal-01197245 , version 1 (11-09-2015)

Identifiers

Cite

Alexis Darrasse, Konstantinos Panagiotou, Olivier Roussel, Michele Soria. Biased Boltzmann samplers and generation of extended linear languages with shuffle. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), Jun 2012, Montreal, Canada. pp.125-140, ⟨10.46298/dmtcs.2989⟩. ⟨hal-01197245⟩
574 View
488 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More