Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2668
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKopecki, Steffende
dc.date.accessioned2010-05-17de
dc.date.accessioned2016-03-31T07:58:55Z-
dc.date.available2010-05-17de
dc.date.available2016-03-31T07:58:55Z-
dc.date.issued2010de
dc.identifier.other324779941de
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-52889de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/2685-
dc.identifier.urihttp://dx.doi.org/10.18419/opus-2668-
dc.description.abstractThe hairpin completion is a natural operation on formal languages which has been inspired by biochemistry and DNA-computing. In this paper we solve two problems which were posed first in 2008 and 2009, respectively, and still left open: 1.) It is known that the iterated hairpin completion of a regular language is not context-free in general, but it was open whether the iterated hairpin completion of a singleton or finite language is regular or at least context-free. We will show that it can be non-context-free. (It is of course context-sensitive.) 2.) A restricted but also very natural variant of the hairpin completion is the bounded hairpin completion. It was unknown whether the iterated bounded hairpin completion of a regular language remains regular. We prove that this is indeed the case. Actually we derive a more general result. We will present a general representation of the iterated bounded hairpin completion for any language using basic operations. Thus, each language class closed under these basic operations is also closed under iterated bounded hairpin completion.en
dc.language.isoende
dc.relation.ispartofseriesTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,2de
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.classificationFormale Sprachede
dc.subject.ddc004de
dc.titleOn the iterated hairpin completionen
dc.typeworkingPaperde
dc.date.updated2013-07-16de
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.opusid5288de
ubs.publikation.typArbeitspapierde
ubs.schriftenreihe.nameTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnikde
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
TR_2010_02.pdf287,96 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.