A linear algorithm for the random sampling from regular languages

DOI10.1007/s00453-010-9446-5zbMath1255.68091MaRDI QIDQ2428675

Omer Giménez, Olivier Bernardi

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9446-5

zbMATH Keywords

regular language; random sampling; combinatorial algorithm; divide-and-conquer

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68Q45: Formal languages and automata

Related Items

Random sampling and reconstruction in multiply generated shift-invariant spaces, Counting and generating permutations in regular classes, Synchronization of Bernoulli sequences on shared letters, Probabilistic divide-and-conquer: deterministic second half

Uses Software

• MersenneTwister

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random generation of words in an algebraic language in linear binary space
• Random generation of trees and other combinatorial objects
• Uniform random generation of decomposable structures using floating-point arithmetic
• Generating words in a context-free language uniformly at random
• A calculus for the random generation of labelled combinatorial structures
• Uniform random generation of words of rational languages
• Uniform Random Generation of Strings in a Context-Free Language
• Uniform random sampling of planar graphs in linear time
• Mersenne twister
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• ECO:a methodology for the enumeration of combinatorial objects