Generating words in a context-free language uniformly at random
From MaRDI portal
Publication:1318776
DOI10.1016/0020-0190(94)90033-7zbMath0795.68120OpenAlexW2085065991MaRDI QIDQ1318776
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
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
