TY - JOUR
AB - © 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.
AU - Brough, T
AU - Ciobanu, L
AU - Elder, M
AU - Zetzsche, G
DA - 2016/01/01
EP - 178
JO - Discrete Mathematics and Theoretical Computer Science
PY - 2016/01/01
SP - 167
TI - Permutations of context-free, ET0L and indexed languages
VL - 17
Y1 - 2016/01/01
Y2 - 2019/11/20
ER -