DOAJ Open Access 2016

Permutations of context-free, ET0L and indexed languages

Tara Brough Laura Ciobanu Murray Elder Georg Zetzsche

Lihat Sumber DOI

Abstrak

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.

Topik & Kata Kunci

Mathematics

Penulis (4)

Tara Brough

Laura Ciobanu

Murray Elder

Georg Zetzsche

Format Sitasi

APA MLA BibTeX

Brough, T., Ciobanu, L., Elder, M., Zetzsche, G. (2016). Permutations of context-free, ET0L and indexed languages. https://doi.org/10.46298/dmtcs.2164

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.2164

Informasi Jurnal

Tahun Terbit: 2016
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.2164
Akses: Open Access ✓