Discrete Mathematics & Theoretical Computer Science, Vol 17, No 3 (2016)

Font Size:  Small  Medium  Large

Permutations of context-free, ET0L and indexed languages

Tara Brough, Laura Ciobanu, Murray Elder, Georg Zetzsche


For a language L, we consider its cyclic closure, and more generally the language Ck(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 Ck. This both sharpens and generalises Brandstädt's result that if L is context-free then Ck(L) is context-sensitive and not context-free in general for k≥3. We also show that the cyclic closure of an indexed language is indexed.

Full Text: PDF PostScript