2025/09/26 by Duncan, Andrew, Elder, Murray, Frenkel, Lisa +1
#20F10 #68Q45 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Group Theory (math.GR)
paper · doi:10.48550/arxiv.2509.22239
We prove that the permutation closure of a multiple context-free language is multiple context-free, which extends work of Okhotin and Sorokin [LATA 2020] who showed closure under cyclic shift, and complements work of Brandstädt [1981, RAIRO Inform. Théor.] (resp. Brough et al. [2016, Discrete Math. Theor. Comput. Sci.]) who showed the same result for regular, context-sensitive, recursively enumerable (resp. EDT0L and ET0L) languages. In contrast to Okhotin and Sorokin who work with grammars, our proof uses restricted tree stack automata due to Denkinger [DLT 2016].