Uniform random generation of decomposable structures using floating-point arithmetic

DOI10.1016/S0304-3975(98)00323-5zbMath0933.68154OpenAlexW2043046702MaRDI QIDQ1292294

Paul Zimmermann, Alain Denise

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)

Related Items (21)

Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers ⋮ Generating labeled planar graphs uniformly at random ⋮ On the lexicographical generation of compressed codes ⋮ Random Deterministic Automata ⋮ Probabilistic divide-and-conquer: deterministic second half ⋮ Uniform Generation in Trace Monoids ⋮ 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 ⋮ Exact-Size Sampling of Enriched Trees in Linear Time ⋮ A linear algorithm for the random sampling from regular languages ⋮ Formulae and Asymptotics for Coefficients of Algebraic Functions ⋮ Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example ⋮ RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP ⋮ Parametric random generation of deterministic tree automata ⋮ A Random Testing Approach Using Pushdown Automata ⋮ Controlled non-uniform random generation of decomposable structures ⋮ Uniform random sampling of planar graphs in linear time ⋮ Enumeration and random generation of accessible automata ⋮ Counting and generating permutations in regular classes ⋮ Random Generation for Finitely Ambiguous Context-free Languages

Uses Software

• gfun
• Maple
• Gaia

Cites Work

• Random generation of words in an algebraic language in linear binary space
• A linear-time algorithm for the generation of trees
• A method and two algorithms on the theory of partitions
• Generating words in a context-free language uniformly at random
• A calculus for the random generation of labelled combinatorial structures
• Uniform generation of a Motzkin word
• Uniform random generation of words of rational languages
• Uniform Random Generation of Strings in a Context-Free Language
• GFUN
• Unnamed Item
• Unnamed Item
• Unnamed Item

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