Open Research Newcastle
Browse

Permutations of context-free, ET0L and indexed languages

Download (286.23 kB)
journal contribution
posted on 2025-05-08, 18:14 authored by Tara Brough, Laura Ciobanu, Murray Elder, Georg Zetzsche
For a language L, we consider its cyclic closure, and more generally the language Ck(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 Ck. This both sharpens and generalises Brandstädt's result that if L is context-free then Ck(L) is context-sensitive and not context-free in general for k=3. We also show that the cyclic closure of an indexed language is indexed.

History

Journal title

Discrete Mathematics & Theoretical Computer Science

Volume

17

Issue

3

Pagination

167-178

Publisher

Chapman & Hall

Language

  • en, English

College/Research Centre

Faculty of Science and Information Technology

School

School of Mathematical and Physical Sciences

Usage metrics

    Publications

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC