A quasi-polynomial-time algorithm for sampling words from a context-free language

DOI10.1006/inco.1997.2621zbMath0879.68065OpenAlexW1972917397MaRDI QIDQ1363787

Steve Mahaney, Z. Sweedyk, Sampath Kannan, Vivek K. Gore, Mark R. Jerrum

Publication date: 17 December 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/53ddde68efdf14201109ca98b990520ea24e4420

zbMATH Keywords

quasi-polynomial-time algorithm

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Related Items

Generating, sampling and counting subclasses of regular tree languages ⋮ The weighted grammar constraint ⋮ Random Generation for Finitely Ambiguous Context-free Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudorandom bits for constant depth circuits
• Random generation of combinatorial structures from a uniform distribution
• Generating words in a context-free language uniformly at random
• The complexity of computing maximal word functions
• Fast Parallel Computation of Polynomials Using Few Processors
• Uniform Random Generation of Strings in a Context-Free Language
• Monte-Carlo approximation algorithms for enumeration problems
• Depth reduction for noncommutative arithmetic circuits
• Probability Inequalities for Sums of Bounded Random Variables
• Preservation of unambiguity and inherent ambiguity in context-free languages
• The Parallel Evaluation of Arithmetic Expressions Without Division