Geodesic
Permutations of context-free, ET0L and indexed languages
Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3.

Voir la notice de l'article provenant de la source Episciences

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ädt'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. 
@article{DMTCS_2016_17_3_a20,
     author = {Brough, Tara and Ciobanu, Laura and Elder, Murray and Zetzsche, Georg},
     title = {Permutations of context-free, {ET0L} and indexed languages},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2015-2016},
     doi = {10.46298/dmtcs.2164},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2164/}
}
TY  - JOUR
AU  - Brough, Tara
AU  - Ciobanu, Laura
AU  - Elder, Murray
AU  - Zetzsche, Georg
TI  - Permutations of context-free, ET0L and indexed languages
JO  - Discrete mathematics & theoretical computer science
PY  - 2015-2016
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2164/
DO  - 10.46298/dmtcs.2164
LA  - en
ID  - DMTCS_2016_17_3_a20
ER  - 
%0 Journal Article
%A Brough, Tara
%A Ciobanu, Laura
%A Elder, Murray
%A Zetzsche, Georg
%T Permutations of context-free, ET0L and indexed languages
%J Discrete mathematics & theoretical computer science
%D 2015-2016
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2164/
%R 10.46298/dmtcs.2164
%G en
%F DMTCS_2016_17_3_a20
Brough, Tara; Ciobanu, Laura; Elder, Murray; Zetzsche, Georg. Permutations of context-free, ET0L and indexed languages. Discrete mathematics & theoretical computer science, Tome 17 (2015-2016) no. 3. doi : 10.46298/dmtcs.2164. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2164/

Cité par Sources :