Non-redundant random generation algorithms for weighted context-free grammars
From MaRDI portal
Publication:391421
DOI10.1016/j.tcs.2013.01.006zbMath1296.68087arXiv1211.0303WikidataQ57221056 ScholiaQ57221056MaRDI QIDQ391421
Yann Ponty, William Andrew Lorenz
Publication date: 10 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1211.0303
random generation; context-free languages; non-redundant generation; recursive random generation; unranking; weighted grammars
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68Q42: Grammars and rewriting systems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Random generation of words in an algebraic language in linear binary space
- Controlled non-uniform random generation of decomposable structures
- Birthday paradox, coupon collectors, caching algorithms and self- organizing search
- A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
- Uniform random generation of decomposable structures using floating-point arithmetic
- Finite range random walk on free groups and homogeneous trees
- A calculus for the random generation of labelled combinatorial structures
- Relax, but don't be too lazy
- Non-uniform random generation of generalized Motzkin paths
- A generic approach for the unranking of labeled combinatorial classes
- Coloring rules for finite trees, and probabilities of monadic second order sentences
- GFUN
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Boltzmann Sampling of Unlabelled Structures
- On Buffon Machines and Numbers