Grammatical Framework and Multiple Context-Free Grammars

Grammatical Framework (GF) [5] is a grammar for-malism originating from logical frameworks for de-pendent type theory. It is already known that the parsing problem for GF is undecidable, which has to do with the possibility to formulate undecidable propositions. But for subclasses of GF, in particular GF with a context-free backbone, parsing is decid-able. Until now the parsing complexity of context-free GF has been unknown, which we aim to change with this article. We show that there is a simple one-to-one corre-spondence between Grammatical Framework with context-free backbone and Multiple Context-Free Grammars (MCFG) [7]. Since the parsing complexity for MCFGs is known to be polynomial in the lengt