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

DOI10.1006/INCO.1997.2621zbMATH Open0879.68065OpenAlexW1972917397MaRDI QIDQ1363787FDOQ1363787

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

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

Recommendations

• A linear algorithm for the random sampling from regular languages
• Generating words in a context-free language uniformly at random
• A polynomial-time approximation algorithm for counting words accepted by an NFA (invited paper)
• A Polynomial Algorithm for the Inference of Context Free Languages
• scientific article; zbMATH DE number 1552330
• scientific article; zbMATH DE number 1670730
• Polynomial time learning of simple deterministic languages via queries and a representative sample
• A new dichotomic algorithm for the uniform random generation of words in regular languages
• The Viterbi algorithm for subsets of stochastic context-free languages
• On lengths of words in context-free languages

zbMATH Keywords

quasi-polynomial-time algorithm

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Generating, sampling and counting subclasses of regular tree languages
• Generating words in a context-free language uniformly at random
• The weighted grammar constraint
• Random Generation for Finitely Ambiguous Context-free Languages
• A linear algorithm for the random sampling from regular languages
• Efficient Computation of Throughput Values of Context-Free Languages
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: A quasi-polynomial-time algorithm for sampling words from a context-free language

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363787)