Permutations of context-free, ET0L and indexed languages - Archive ouverte HAL Access content directly
Journal Articles Discrete Mathematics and Theoretical Computer Science Year : 2016

## Permutations of context-free, ET0L and indexed languages

(1) , (2) , (3) , (4)
1
2
3
4
Tara Brough
• Function : Author
Laura Ciobanu
• Function : Author
• PersonId : 965584
Murray Elder
• Function : Author
Georg Zetzsche

#### 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ä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.

#### Domains

Computer Science [cs] Discrete Mathematics [cs.DM]

### Dates and versions

hal-01352858 , version 1 (16-08-2016)

### Identifiers

• HAL Id : hal-01352858 , version 1
• DOI :

### Cite

Tara Brough, Laura Ciobanu, Murray Elder, Georg Zetzsche. Permutations of context-free, ET0L and indexed languages. Discrete Mathematics and Theoretical Computer Science, 2016, Vol. 17 no. 3 (3), pp.167-178. ⟨10.46298/dmtcs.2164⟩. ⟨hal-01352858⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

158 View