arXiv Open Access 2025

Permutation closure for multiple context-free languages

Andrew Duncan Murray Elder Lisa Frenkel Mengfan Lyu

Lihat Sumber

Abstrak

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 under \emph{cyclic shift}, and complements work of Brandstädt [1981, RAIRO Inform. Théor.] (resp. Brough \emph{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].

Topik & Kata Kunci

cs.FL math.GR

Penulis (4)

Andrew Duncan

Murray Elder

Lisa Frenkel

Mengfan Lyu

Format Sitasi

APA MLA BibTeX

Duncan, A., Elder, M., Frenkel, L., Lyu, M. (2025). Permutation closure for multiple context-free languages. https://arxiv.org/abs/2509.22239

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2025
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓