pith. sign in

arxiv: 1604.05431 · v2 · pith:KOC2V7HMnew · submitted 2016-04-19 · 💻 cs.FL

Permutations of context-free, ET0L and indexed languages

classification 💻 cs.FL
keywords context-freeindexedlanguageclosurecyclicet0llanguageswords
0
0 comments X
read the original 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\"adt'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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.