A new dichotomic algorithm for the uniform random generation of words in regular languages

DOI10.1016/j.tcs.2012.07.025zbMath1296.68095OpenAlexW1983360325MaRDI QIDQ391418

Alain Denise, Marie-Claude Gaudel, Johan Oudinet

Publication date: 10 January 2014

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.07.025

zbMATH Keywords

regular languageslarge automatarandom generation of words

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated ⋮ Counting and generating permutations in regular classes ⋮ Unnamed Item

Uses Software

• gmp
• Boost
• BGL

Cites Work

• Unnamed Item
• Random generation of words in an algebraic language in linear binary space
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• Uniform random generation of decomposable structures using floating-point arithmetic
• A calculus for the random generation of labelled combinatorial structures
• On the solution of linear recurrence equations
• Uniform Random Generation of Strings in a Context-Free Language
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Boltzmann Sampling of Unlabelled Structures