Uniform random generation of decomposable structures using floating-point arithmetic

DOI10.1016/S0304-3975(98)00323-5MaRDI QIDQ1292294zbMATHOpenAlexFDO

Authors Alain Denise, Paul Zimmermann

Publication date 21 June 1999

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(98)00323-5

zbMATH Keywords

combinatorial algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• Controlled non-uniform random generation of decomposable structures
• A calculus for the random generation of labelled combinatorial structures
• Uniform random generation of words of rational languages

Cites work

• scientific article; zbMATH DE number 3934391 (Why is no real title available?)
• scientific article; zbMATH DE number 52125 (Why is no real title available?)
• scientific article; zbMATH DE number 910913 (Why is no real title available?)
• A calculus for the random generation of labelled combinatorial structures
• A linear-time algorithm for the generation of trees
• A method and two algorithms on the theory of partitions
• GFUN
• Generating words in a context-free language uniformly at random
• Random generation of words in an algebraic language in linear binary space
• Uniform Random Generation of Strings in a Context-Free Language
• Uniform generation of a Motzkin word
• Uniform random generation of words of rational languages

Cited in

(22)

• On the lexicographical generation of compressed codes
• Random deterministic automata
• A new dichotomic algorithm for the uniform random generation of words in regular languages
• Non-redundant random generation algorithms for weighted context-free grammars
• Faster FPTASes for counting and random generation of knapsack solutions
• Probabilistic divide-and-conquer: a new exact simulation method, with integer partitions as an example
• Generating labeled planar graphs uniformly at random
• Controlled non-uniform random generation of decomposable structures
• RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP
• Formulae and asymptotics for coefficients of algebraic functions
• Exact-Size Sampling of Enriched Trees in Linear Time
• Parametric random generation of deterministic tree automata
• Uniform generation in trace monoids
• Random Generation for Finitely Ambiguous Context-free Languages
• Counting and generating permutations in regular classes
• Enumeration and random generation of accessible automata
• A random testing approach using pushdown automata
• Holonomic equations and efficient random generation of binary trees
• Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
• A linear algorithm for the random sampling from regular languages
• Uniform random sampling of planar graphs in linear time
• Probabilistic divide-and-conquer: deterministic second half

Describes a project that uses

Uses Software

• gfun
• Maple
• Gaia

This page was built for publication: Uniform random generation of decomposable structures using floating-point arithmetic

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