A linear algorithm for the random sampling from regular languages
From MaRDI portal
Publication:2428675
DOI10.1007/s00453-010-9446-5zbMath1255.68091OpenAlexW2001959333MaRDI 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
Related Items (9)
Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers ⋮ Property-directed verification and robustness certification of recurrent neural networks ⋮ Probabilistic divide-and-conquer: deterministic second half ⋮ Approximate NFA universality and related problems motivated by information theory ⋮ Random sampling and reconstruction in multiply generated shift-invariant spaces ⋮ Synchronization of Bernoulli sequences on shared letters ⋮ Non-uniform random sampling and reconstruction in signal spaces with finite rate of innovation ⋮ Counting and generating permutations in regular classes ⋮ Unnamed Item
Uses Software
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: A linear algorithm for the random sampling from regular languages
