A substitution lemma for multiple context-free languages

Abstract

We present a new criterion for proving that a language is not multiple context-free, which we call a Substitution Lemma. We apply it to show a sample selection of languages are not multiple context-free, including the word problem of $F_2\times F_2$. Our result is in contrast to Kanazawa et al. [2014, Theory Comput. Syst.] who proved that it was not possible to generalise the standard pumping lemma for context-free languages to multiple context-free languages, and Kanazawa [2019, Inform. and Comput.] who showed a weak variant of generalised Ogden's lemma does not apply to multiple context-free languages. We also show that groups with multiple context-free word problem have rational subset membership and intersection problems.

Categories