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

DOI10.1016/0020-0190(95)00025-8MaRDI QIDQ673672zbMATH OpenOpenAlexFDO

Authors 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

Analysis of algorithmsGenerating functionsContext-free languagesUniform random generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Generating words in a context-free language uniformly at random
• Random Generation for Finitely Ambiguous Context-free Languages
• Uniform random generation of words of rational languages

Cites work

• scientific article; zbMATH DE number 3755865 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• A calculus for the random generation of labelled combinatorial structures
• Algebraic languages and polyominoes enumeration
• Calcul pratique des coefficients de Taylor d'une fonction algébrique
• Formal languages and enumeration
• The random generation of underdiagonal walks
• Uniform Random Generation of Strings in a Context-Free Language
• Uniform generation of a Motzkin word

Cited in

(18)

• A new dichotomic algorithm for the uniform random generation of words in regular languages
• Non-redundant random generation algorithms for weighted context-free grammars
• Uniform random generation of words of rational languages
• scientific article; zbMATH DE number 2051177 (Why is no real title available?)
• Heads-or-tails drawing of Fibonacci words
• Uniform random generation of decomposable structures using floating-point arithmetic
• Random and uniform generation of words
• Taming reluctant random walks in the positive quadrant
• Controlled non-uniform random generation of decomposable structures
• Bounded length UCFG equivalence
• scientific article; zbMATH DE number 1688372 (Why is no real title available?)
• Random Generation for Finitely Ambiguous Context-free Languages
• A random testing approach using pushdown automata
• scientific article; zbMATH DE number 1552330 (Why is no real title available?)
• Linear delay enumeration and monadic second-order logic
• A linear algorithm for the random sampling from regular languages
• Multi-dimensional Boltzmann sampling of languages
• Generating words in a context-free language uniformly at random

This page was built for publication: Random generation of words in an algebraic language in linear binary space

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