Skip to Main content Skip to Navigation
Journal articles

Permutations of context-free, ET0L and indexed languages

Abstract : For a language $L$, we consider its cyclic closure, and more generally the language $C^{k}(L)$, which consists of all words obtained by partitioning words from $L$ into $k$ factors and permuting them. We prove that the classes of ET0L and EDT0L languages are closed under the operators $C^k$. This both sharpens and generalises Brandstädt's result that if $L$ is context-free then $C^{k}(L)$ is context-sensitive and not context-free in general for $k \geq 3$. We also show that the cyclic closure of an indexed language is indexed.
Document type :
Journal articles
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Tuesday, August 16, 2016 - 2:46:43 PM
Last modification on : Friday, April 30, 2021 - 9:53:26 AM
Long-term archiving on: : Thursday, November 17, 2016 - 10:29:57 AM


Explicit agreement for this submission


  • HAL Id : hal-01352858, version 1


Tara Brough, Laura Ciobanu, Murray Elder, Georg Zetzsche. Permutations of context-free, ET0L and indexed languages. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.167-178. ⟨hal-01352858⟩



Record views


Files downloads