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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2016, Vol. 17 no. 3 (3), pp.167-178
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01352858
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 16 août 2016 - 14:46:43
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : jeudi 17 novembre 2016 - 10:29:57

Fichier

2751-9926-1-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : hal-01352858, version 1

Citation

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〉

Partager

Métriques

Consultations de la notice

109

Téléchargements de fichiers

280