Generating words in a context-free language uniformly at random

DOI10.1016/0020-0190(94)90033-7zbMath0795.68120OpenAlexW2085065991MaRDI QIDQ1318776

Harry G. Mairson

Publication date: 4 April 1994

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

Full work available at URL: https://doi.org/10.1016/0020-0190(94)90033-7

zbMATH Keywords

context-free languagecontext-free grammarbit complexityword generation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items

Uniform random generation of words of rational languages ⋮ ON THE AVERAGE STATE COMPLEXITY OF PARTIAL DERIVATIVE AUTOMATA: AN ANALYTIC COMBINATORICS APPROACH ⋮ A quasi-polynomial-time algorithm for sampling words from a context-free language ⋮ Random and uniform generation of words ⋮ Left is Better Than Right for Reducing Nondeterminism of NFAs ⋮ A linear algorithm for the random sampling from regular languages ⋮ Location automata for regular expressions with shuffle and intersection ⋮ Ranking and unranking left szilard languages ⋮ Linear delay enumeration and monadic second-order logic ⋮ Antimirov and Mosses’s Rewrite System Revisited ⋮ Generating random binary trees -- a survey ⋮ ANTIMIROV AND MOSSES'S REWRITE SYSTEM REVISITED ⋮ Uniform random generation of decomposable structures using floating-point arithmetic ⋮ Random Generation for Finitely Ambiguous Context-free Languages

Cites Work

• Unnamed Item
• Uniform Random Generation of Strings in a Context-Free Language