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

DOI10.1006/INCO.1997.2621MaRDI QIDQ1363787zbMATH OpenOpenAlexFDO

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

Publication date 17 December 1997

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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)

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

Cites work

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

Cited in

(13)

• Non-redundant random generation algorithms for weighted context-free grammars
• Generating, sampling and counting subclasses of regular tree languages
• Generating words in a context-free language uniformly at random
• Multi-dimensional Boltzmann sampling of languages
• The weighted grammar constraint
• Random Generation for Finitely Ambiguous Context-free Languages
• Checking whether two unambiguous context-free grammars describe the same set of strings of length n
• An FPRAS for two terminal reliability in directed acyclic graphs
• A linear algorithm for the random sampling from regular languages
• Efficient Computation of Throughput Values of Context-Free Languages
• scientific article; zbMATH DE number 1836426 (Why is no real title available?)
• Random graph generation in context-free graph languages
• scientific article; zbMATH DE number 1552330 (Why is no real title available?)

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)