2
$\begingroup$

Let $L\subset \Sigma^*$ be a context-free language. The $n$-slice is the intersection $L\cap \Sigma^n$ for a non-negative integer $n$.

Is there a polynomial-time algorithm for uniformly sampling from the $n$-slice of a context-free language?

A quasipolynomial time algorithm is presented in "A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language".

Improve this question
$\endgroup$
2
  • $\begingroup$ So, do you ask for an improvement over an existing research paper in MO answer? Why do you think such an improvement exists at first place? $\endgroup$
    – Max Alekseyev
    Commented Aug 2, 2021 at 13:05
  • $\begingroup$ This question is more suitable for cstheory.stackexchange.com $\endgroup$
    – domotorp
    Commented Aug 2, 2021 at 13:30

0

Reset to default

You must log in to answer this question.