Uniform Random Generation of Strings in a Context-Free Language

DOI10.1137/0212044zbMath0524.68046OpenAlexW1996684294MaRDI QIDQ3036723

Timothy J. Hickey, Jacques Cohen

Publication date: 1983

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0212044

zbMATH Keywords

generating functionsconvolutioncontext-free languageenumeration problemsuniform random generationbalanced parenthesis stringsleftmost derivations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20)

Related Items (24)

Simplifying regular expressions further ⋮ Uniform generation of forests of restricted height ⋮ A calculus for the random generation of labelled combinatorial structures ⋮ Directed column-convex polyominoes by recurrence relations ⋮ Analytic models and ambiguity of context-free languages ⋮ The random generation of underdiagonal walks ⋮ Uniform random generation of words of rational languages ⋮ A quasi-polynomial-time algorithm for sampling words from a context-free language ⋮ Random and uniform generation of words ⋮ A new dichotomic algorithm for the uniform random generation of words in regular languages ⋮ A linear algorithm for the random sampling from regular languages ⋮ Formulae and Asymptotics for Coefficients of Algebraic Functions ⋮ Automatic average-case analysis of algorithms ⋮ Uniform random generation of expressions respecting algebraic identities ⋮ Hybrid one-dimensional reversible cellular automata are regular ⋮ Random generation of words in an algebraic language in linear binary space ⋮ A Random Testing Approach Using Pushdown Automata ⋮ Animaux et arbres guingois. (Animals and guingois trees) ⋮ Ranking and unranking left szilard languages ⋮ Linear delay enumeration and monadic second-order logic ⋮ 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 ⋮ Random Generation for Finitely Ambiguous Context-free Languages

This page was built for publication: Uniform Random Generation of Strings in a Context-Free Language