A linear algorithm for the random sampling from regular languages

DOI10.1007/S00453-010-9446-5MaRDI QIDQ2428675zbMATH OpenOpenAlexFDO

Authors Olivier Bernardi, Omer Giménez

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

random samplingregular languagecombinatorial algorithmdivide-and-conquer

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Nonnumerical algorithms (68W05)

Recommendations

• A quasi-polynomial-time algorithm for sampling words from a context-free language
• A new dichotomic algorithm for the uniform random generation of words in regular languages
• Heads-or-tails drawing of Fibonacci words
• scientific article; zbMATH DE number 2051177
• Publication:4886090
• Generating words in a context-free language uniformly at random
• Uniform random generation of words of rational languages
• Random generation of words in an algebraic language in linear binary space
• Non-redundant random generation algorithms for weighted context-free grammars
• Random Generation for Finitely Ambiguous Context-free Languages

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 1552330 (Why is no real title available?)
• scientific article; zbMATH DE number 910913 (Why is no real title available?)
• scientific article; zbMATH DE number 3303655 (Why is no real title available?)
• A calculus for the random generation of labelled combinatorial structures
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• ECO:a methodology for the enumeration of combinatorial objects
• Generating words in a context-free language uniformly at random
• Mersenne twister
• Random generation of trees and other combinatorial objects
• Random generation of words in an algebraic language in linear binary space
• Uniform Random Generation of Strings in a Context-Free Language
• Uniform random generation of decomposable structures using floating-point arithmetic
• Uniform random generation of words of rational languages
• Uniform random sampling of planar graphs in linear time

Cited in

(14)

• A new dichotomic algorithm for the uniform random generation of words in regular languages
• Heads-or-tails drawing of Fibonacci words
• scientific article; zbMATH DE number 2051177 (Why is no real title available?)
• Probabilistic divide-and-conquer: deterministic second half
• Synchronization of Bernoulli sequences on shared letters
• scientific article; zbMATH DE number 7204953 (Why is no real title available?)
• Property-directed verification and robustness certification of recurrent neural networks
• Counting and generating permutations in regular classes
• Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
• Non-uniform random sampling and reconstruction in signal spaces with finite rate of innovation
• Random sampling and reconstruction in multiply generated shift-invariant spaces
• Approximate NFA universality and related problems motivated by information theory
• scientific article; zbMATH DE number 910913 (Why is no real title available?)
• A quasi-polynomial-time algorithm for sampling words from a context-free language

Describes a project that uses

Uses Software

• MersenneTwister

This page was built for publication: A linear algorithm for the random sampling from regular languages

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