Random generation of words in an algebraic language in linear binary space

DOI10.1016/0020-0190(95)00025-8zbMath0875.68532OpenAlexW2059396087MaRDI QIDQ673672

Massimiliano Goldwurm

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00025-8

zbMATH Keywords

Generating functionsAnalysis of algorithmsContext-free languagesUniform random generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Uniform random generation of words of rational languages ⋮ Random and uniform generation of words ⋮ A new dichotomic algorithm for the uniform random generation of words in regular languages ⋮ Non-redundant random generation algorithms for weighted context-free grammars ⋮ Taming reluctant random walks in the positive quadrant ⋮ A linear algorithm for the random sampling from regular languages ⋮ A Random Testing Approach Using Pushdown Automata ⋮ Linear delay enumeration and monadic second-order logic ⋮ Controlled non-uniform random generation of decomposable structures ⋮ Uniform random generation of decomposable structures using floating-point arithmetic ⋮ Random Generation for Finitely Ambiguous Context-free Languages

Cites Work

• Formal languages and enumeration
• A calculus for the random generation of labelled combinatorial structures
• Uniform generation of a Motzkin word
• Algebraic languages and polyominoes enumeration
• The random generation of underdiagonal walks
• Calcul pratique des coefficients de Taylor d'une fonction algébrique
• Uniform Random Generation of Strings in a Context-Free Language
• Unnamed Item
• Unnamed Item