Multi-dimensional Boltzmann sampling of languages

MaRDI QIDQ2959895zbMATH OpenFDO

Authors Olivier Bodini, Yann Ponty

Publication date 10 February 2017

Full work available at URL http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAM0104

zbMATH Keywords

context-free languagesrandom generationBoltzmann sampling

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial probability (60C05) Combinatorial aspects of tessellation and tiling problems (05B45)

Recommendations

• scientific article; zbMATH DE number 1552330
• A quasi-polynomial-time algorithm for sampling words from a context-free language
• Non-redundant random generation algorithms for weighted context-free grammars
• Random generation of words in an algebraic language in linear binary space
• Generating words in a context-free language uniformly at random

Cited in

(19)

• Boltzmann samplers for \(v\)-balanced cycles
• Non-redundant random generation algorithms for weighted context-free grammars
• Formulae and asymptotics for coefficients of algebraic functions
• Generating functions for lattice paths with several forbidden patterns
• Asymptotic properties of random unlabelled block-weighted graphs
• Language sampling for universal grammars
• Boltzmann samplers for first-order differential specifications
• Counting and generating permutations in regular classes
• Exact-Size Sampling of Enriched Trees in Linear Time
• Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
• Biased Boltzmann samplers and generation of extended linear languages with shuffle
• Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels
• Random generation of source vectors with a fixed preponderant property
• Random-bit optimal uniform sampling for rooted planar trees with given sequence of degrees and applications
• Radii of convergence of algebraic power series
• Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models
• Efficient random sampling of binary and unary-binary trees via holonomic equations
• On the number of unary-binary tree-like structures with restrictions on the unary height
• scientific article; zbMATH DE number 1552330 (Why is no real title available?)

This page was built for publication: Multi-dimensional Boltzmann sampling of languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2959895)