Uniform Random Generation of Strings in a Context-Free Language
From MaRDI portal
Publication:3036723
DOI10.1137/0212044zbMath0524.68046MaRDI QIDQ3036723
Jacques Cohen, Timothy J. Hickey
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
generating functions; convolution; context-free language; enumeration problems; uniform random generation; balanced parenthesis strings; leftmost derivations
Related Items
Ranking and unranking left szilard languages, A new dichotomic algorithm for the uniform random generation of words in regular languages, Random generation of words in an algebraic language in linear binary space, Animaux et arbres guingois. (Animals and guingois trees), Linear delay enumeration and monadic second-order logic, Analytic models and ambiguity of context-free languages, Automatic average-case analysis of algorithms, Uniform random generation of expressions respecting algebraic identities, 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, Uniform generation of forests of restricted height, A calculus for the random generation of labelled combinatorial structures, Uniform random generation of words of rational languages, A quasi-polynomial-time algorithm for sampling words from a context-free language, The random generation of underdiagonal walks, Random and uniform generation of words, A linear algorithm for the random sampling from regular languages, Hybrid one-dimensional reversible cellular automata are regular, A Random Testing Approach Using Pushdown Automata, Random Generation for Finitely Ambiguous Context-free Languages
