Non-redundant random generation algorithms for weighted context-free grammars

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

zbMATH Keywords

random generation; context-free languages; non-redundant generation; recursive random generation; unranking; weighted grammars

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Uses Software

• gfun
• GenRGenS

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