1
$\begingroup$

Let A and B be two determinstic context-free grammar, and let N be an integer: What's the complexity of deciding if the intersection of the languages accepted by A and B over all strings of length less than N is empty?

It's easy to check that the problem is PSPACE-Hard for general CFGs. The reduction can be done from intersection emptiness problem of a set of Deterministic Finite Automata. The proof relies heavily on the unambiguity of the construction though. For Determinstic CFGs, I can't manage to find the solution. We know that the unbounded version of the problem is undecidable, though. This makes me think that the problem is at least NP-Hard. However, I couldn't derive a proof for this.

Thanks for your help in advance

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Mark-Jan Nederhof, Giorgio Satta: The language intersection problem for non-recursive context-free grammars. Inf. Comput. 192(2): 172-184 (2004) proved that:

Theorem 1. Let the input consist of two non-recursive deterministic CFGs. The problem of deciding non-emptiness of the intersection of the two generated languages is PSPACE-hard.

The theorem holds for non-recursive (deterministic) CF grammars, so your problem is simply a generalization: using the same construction, just set $N$ large enough to include the longest string (i.e. the max number of steps of the "simulated" LBA).

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks for your answer. A polynomial-time reduction from the LBA problem will require N to be set exponentially large with respect to the string w of the input of the LBA. Therefore, the PSpace-Hardness result holds only if N is given in binary format. I wonder about the case when N is given in unary format, which i think is more interesting. $\endgroup$
    – RockyBilboa
    Commented Mar 27, 2022 at 10:59
  • $\begingroup$ In that case I think it is NP-hard (just generate the non-recursive grammars for the polytime verifier) $\endgroup$
    – Marzio De Biasi
    Commented Mar 27, 2022 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.