A substitution lemma for multiple context-free languages
International Journal of Algebra and Computation · 05.08.2026 · 1-35
DOI: 10.1142/s0218196726500463 ↗Kurz gefasst
Fachartikel in der Zeitschrift International Journal of Algebra and Computation, online erschienen am 05.08.2026. Verfasst von Andrew Duncan und 3 weiteren Autor:innen.
Abstract (Originalsprache)
In this paper, 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 [Formula: see text]. 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 generalized to multiple context-free languages, and that weak variants of generalized Ogden’s lemma do not apply to multiple context-free languages.
Zitieren
APA
Duncan, A., Elder, M., Frenkel, L., & Lyu, M. (2026). A substitution lemma for multiple context-free languages. International Journal of Algebra and Computation, 1-35. https://doi.org/10.1142/s0218196726500463
Vancouver
Duncan A, Elder M, Frenkel L, Lyu M. A substitution lemma for multiple context-free languages. International Journal of Algebra and Computation. 2026:1-35. doi:10.1142/s0218196726500463
BibTeX
@article{Duncan2026,
author = {Duncan, Andrew and Elder, Murray and Frenkel, Lisa and Lyu, Mengfan},
title = {A substitution lemma for multiple context-free languages},
journal = {International Journal of Algebra and Computation},
year = {2026},
pages = {1--35},
doi = {10.1142/s0218196726500463}
}
EUVIMED