Showing cs.FLShow all
2 papers · 1 filter
cs.FL2025
Permutation closure for multiple context-free languages
Andrew Duncan, Murray Elder, Lisa Frenkel +1
We prove that the \emph{permutation closure} of a multiple context-free language is multiple context-free, which extends work of Okhotin and Sorokin [LATA 2020] who showed closure…
cs.FL2025
A substitution lemma for multiple context-free languages
Andrew Duncan, Murray Elder, Lisa Frenkel +1
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 n…