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

DOI10.1016/0020-0190(95)00025-8zbMath0875.68532MaRDI 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 functions; Analysis of algorithms; Context-free languages; Uniform random generation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

A new dichotomic algorithm for the uniform random generation of words in regular languages, Non-redundant random generation algorithms for weighted context-free grammars, Controlled non-uniform random generation of decomposable structures, Linear delay enumeration and monadic second-order logic, Uniform random generation of decomposable structures using floating-point arithmetic, Uniform random generation of words of rational languages, Taming reluctant random walks in the positive quadrant, Random and uniform generation of words, A linear algorithm for the random sampling from regular languages, A Random Testing Approach Using Pushdown Automata, 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