EUVIMEDEUVIMED entdecken
Crossref

A substitution lemma for multiple context-free languages

Andrew Duncan, Murray Elder, Lisa Frenkel, Mengfan Lyu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →