Algorithmic and computational advances in geometric group theory
Indicators
1224
Views
1852
Downloads
Permutations of context-free, ET0L and indexed languages
Tara Brough (1) (2) (3), Laura Ciobanu (4) (5), Murray Elder (6) (7), Georg Zetzsche (8)
(1) Universidade de Lisboa = University of Lisbon
(2) Universidade de Lisboa = University of Lisbon = Université de Lisbonne
(3) Universidade de Lisboa = University of Lisbon = Université de Lisbonne [Lisboa]
(4) Université de Neuchâtel
(5) Université de Neuchâtel = University of Neuchatel
(6) University of Newcastle [Australia]
(7) University of Newcastle [Callaghan, Australia]
(8) Laboratoire Spécification et Vérification [Cachan]
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.
