<p><a href="https://doi.org/10.1016/j.ic.2004.03.004" rel="nofollow noreferrer">Mark-Jan Nederhof, Giorgio Satta: The language intersection problem for non-recursive context-free grammars. Inf. Comput. 192(2): 172-184 (2004)</a> proved that:</p>
<p><strong>Theorem 1.</strong> 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.</p>
<p>The theorem holds for non-recursive (deterministic) CF grammars, so your problem is simply a generalization: using the same construction, just set <span class="math-container">$N$</span> large enough to include the longest string (i.e. the max number of steps of the &quot;simulated&quot; LBA).</p>

CC BY-SA 4.0
2022-03-27T10:59:27.860Z
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.
RockyBilboa
CC BY-SA 4.0
2022-03-27T11:14:20.333Z
In that case I think it is NP-hard (just generate the non-recursive grammars for the polytime verifier)
Marzio De Biasi
CC BY-SA 4.0
2022-03-26T23:47:39.953Z
2022-03-26T23:47:39.953Z
Marzio De Biasi
<p>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?</p>
<p>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.</p>
<p>Thanks for your help in advance</p>

<cc.complexity-theory><fl.formal-languages><automata-theory><context-free>
Bounded non-emptiness intersection of deterministic context-free grammars
RockyBilboa
# Bounded non-emptiness intersection of deterministic context-free grammars

(Asked by: username_0 on 2022-03-25)

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

**Tags:** cc.complexity-theory, fl.formal-languages, automata-theory, context-free

---

## 1 answers

### Answer by username_1 on 2022-03-26. Score: 1

[Mark-Jan Nederhof, Giorgio Satta: The language intersection problem for non-recursive context-free grammars. Inf. Comput. 192(2): 172-184 (2004)](https://doi.org/10.1016/j.ic.2004.03.004) 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).

> **Comments:**
> **username_0**: 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.  
> **username_1**: In that case I think it is NP-hard (just generate the non-recursive grammars for the polytime verifier)  

---

