Uniform Random Generation of Strings in a Context-Free Language

DOI10.1137/0212044zbMATH Open0524.68046OpenAlexW1996684294MaRDI QIDQ3036723FDOQ3036723

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

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)