Permutation closure for multiple context-free languages
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908561178624000 |
|---|---|
| author | Duncan, Andrew Elder, Murray Frenkel, Lisa Lyu, Mengfan |
| author_facet | Duncan, Andrew Elder, Murray Frenkel, Lisa Lyu, Mengfan |
| contents | 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]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_22239 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Permutation closure for multiple context-free languages Duncan, Andrew Elder, Murray Frenkel, Lisa Lyu, Mengfan Formal Languages and Automata Theory Group Theory 20F10, 68Q45 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]. |
| title | Permutation closure for multiple context-free languages |
| topic | Formal Languages and Automata Theory Group Theory 20F10, 68Q45 |
| url | https://arxiv.org/abs/2509.22239 |