formal language theory

A substitution lemma for multiple context-free languages

arXiv:2509.02117

summary

The paper introduces a Substitution Lemma as a necessary condition for an infinite language to be multiple context‑free, uses it to prove that several languages—including the word problem of the group F₂×F₂—are not multiple context‑free, and shows that groups with a multiple context‑free word problem have a decidable rational subset membership problem.

Abstract

We present a necessary condition for an infinite language to be 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 the group . We also show that groups with multiple context-free word problem have decidable rational subset membership problem. Our result contrasts with previous work showing that the standard pumping lemma for context-free languages cannot be generalised to multiple context-free languages, and that weak variants of generalised Ogden's lemma do not apply to multiple context-free languages.

27 pages, 6 figures, 2 tables. Small edits made

Topics & keywords

#multiple context-free languages#substitution lemma#word problem#group theory#rational subset membershipsubstitution lemmamultiple context-freepumping lemmaOgden's lemmadecidable rational subset membershipF2×F2
A substitution lemma for multiple context-free languages · wovepaper