A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity

Stefan Mengel, Harry Vinall-Smeeth

Motivated by recent connections to factorised databases, we analyse the efficiency of representations by context free grammars (CFGs). Concretely, we prove a recent conjecture by K…