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 k 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 Determinstic 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

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