Computing the longest common prefix of a context-free language in polynomial time

Michael Luttenberger, Raphaela Palenta, Helmut Seidl

We present two structural results concerning longest common prefixes of non-empty languages. First, we show that the longest common prefix of the language generated by a context-fr…