Tara Brough ; Laura Ciobanu ; Murray Elder ; Georg Zetzsche - Permutations of context-free, ET0L and indexed languages

dmtcs:2164 - Discrete Mathematics & Theoretical Computer Science, May 31, 2016, Vol. 17 no. 3 - https://doi.org/10.46298/dmtcs.2164
Permutations of context-free, ET0L and indexed languages

Authors: Tara Brough ORCID-iD1; Laura Ciobanu 2; Murray Elder 3,4; Georg Zetzsche ORCID-iD5

  • 1 Universidade de Lisboa = University of Lisbon
  • 2 Université de Neuchâtel
  • 3 University of Newcastle [Australia]
  • 4 University of Newcastle [Callaghan, Australia]
  • 5 Laboratoire Spécification et Vérification [Cachan]

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.

Volume: Vol. 17 no. 3
Section: Automata, Logic and Semantics
Published on: May 31, 2016
Submitted on: January 5, 2015
Keywords: cyclic closure, context-free,ET0L, EDT0L, indexed,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Formal languages and decision problems in groups; Funder: Swiss National Science Foundation; Code: 144681
  • Algorithmic and computational advances in geometric group theory; Funder: Swiss National Science Foundation; Code: FT110100178

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1016/0304-3975(82)90009-3
  • 10.1016/0304-3975(82)90009-3
The IO- and OI-hierarchies

Consultation statistics

This page has been seen 384 times.
This article's PDF has been downloaded 683 times.