Permutations of context-free, ET0L and indexed languages

Brough, T; Ciobanu, L; Elder, M; Zetzsche, G

Permutations of context-free, ET0L and indexed languages

Brough, T Ciobanu, L Elder, M

Zetzsche, G

Permalink

Publication Type:: Journal Article
Citation:: Discrete Mathematics and Theoretical Computer Science, 2016, 17 (3), pp. 167 - 178
Issue Date:: 2016-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (286.23 kB)

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Brough, T	en_US
dc.contributor.author	Ciobanu, L	en_US
dc.contributor.author	Elder, M https://orcid.org/0000-0002-2438-3945	en_US
dc.contributor.author	Zetzsche, G	en_US
dc.date.issued	2016-01-01	en_US
dc.identifier.citation	Discrete Mathematics and Theoretical Computer Science, 2016, 17 (3), pp. 167 - 178	en_US
dc.identifier.issn	1462-7264	en_US
dc.identifier.uri	http://hdl.handle.net/10453/96210
dc.description.abstract	© 2016 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France. 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.	en_US
dc.relation.ispartof	Discrete Mathematics and Theoretical Computer Science	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	Permutations of context-free, ET0L and indexed languages	en_US
dc.type	Journal Article
utslib.citation.volume	3	en_US
utslib.citation.volume	17	en_US
utslib.for	01 Mathematical Sciences	en_US
utslib.for	08 Information and Computing Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Science
pubs.organisational-group	/University of Technology Sydney/Faculty of Science/School of Mathematical and Physical Sciences
utslib.copyright.status	open_access
pubs.issue	3	en_US
pubs.publication-status	Published	en_US
pubs.volume	17	en_US

Abstract:

© 2016 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France. 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.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/96210