Permutations of context-free, ET0L and indexed languages

Publication Type:
Journal Article
Citation:
Discrete Mathematics and Theoretical Computer Science, 2016, 17 (3), pp. 167 - 178
Issue Date:
2016-01-01
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
4740.pdfPublished Version286.23 kB
Adobe PDF
© 2016 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France. 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.
Please use this identifier to cite or link to this item: