Uniform Random Generation of Strings in a Context-Free Language

DOI10.1137/0212044zbMATH Open0524.68046OpenAlexW1996684294MaRDI QIDQ3036723FDOQ3036723

Authors 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

convolutiongenerating functionscontext-free languageuniform random generationenumeration problemsbalanced parenthesis stringsleftmost derivations

Mathematics Subject Classification ID

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

Cited in

(25)

• A calculus for the random generation of labelled combinatorial structures
• A new dichotomic algorithm for the uniform random generation of words in regular languages
• Uniform random generation of words of rational languages
• The random generation of underdiagonal walks
• Random generation of words in an algebraic language in linear binary space
• Automatic average-case analysis of algorithms
• Uniform random generation of decomposable structures using floating-point arithmetic
• A quasi-polynomial-time algorithm for sampling words from a context-free language
• Random and uniform generation of words
• Uniform generation of forests of restricted height
• Simplifying regular expressions further
• Randomized Synthesis for Diversity and Cost Constraints with Control Improvisation
• Directed column-convex polyominoes by recurrence relations
• Hybrid one-dimensional reversible cellular automata are regular
• Ranking and unranking left szilard languages
• Formulae and asymptotics for coefficients of algebraic functions
• Animaux et arbres guingois. (Animals and guingois trees)
• Random Generation for Finitely Ambiguous Context-free Languages
• A random testing approach using pushdown automata
• Linear delay enumeration and monadic second-order logic
• Uniform random generation of expressions respecting algebraic identities
• A linear algorithm for the random sampling from regular languages
• Generating words in a context-free language uniformly at random
• Random generation of trees and other combinatorial objects
• Analytic models and ambiguity of context-free languages

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

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