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

DOI10.1016/0020-0190(95)00025-8zbMATH Open0875.68532OpenAlexW2059396087MaRDI QIDQ673672FDOQ673672

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

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

zbMATH Keywords

Analysis of algorithmsGenerating functionsContext-free languagesUniform random generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

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
• Heads-or-tails drawing of Fibonacci words
• Title not available (Why is that?)
• Controlled non-uniform random generation of decomposable structures
• Linear delay enumeration and monadic second-order logic
• 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
• Multi-dimensional Boltzmann sampling of languages
• Uniform random generation of words of rational languages
• A random testing approach using pushdown automata
• Random Generation for Finitely Ambiguous Context-free Languages
• Title not available (Why is that?)
• Taming reluctant random walks in the positive quadrant
• A linear algorithm for the random sampling from regular languages
• Bounded length UCFG equivalence
• Title not available (Why is that?)

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)