Permutations of context-free, ET0L and indexed languages
Tara Brough, Laura Ciobanu, Murray Elder, Georg Zetzsche
Abstract
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