Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2673
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDiekert, Volkerde
dc.contributor.authorKopecki, Steffende
dc.date.accessioned2010-07-14de
dc.date.accessioned2016-03-31T07:58:57Z-
dc.date.available2010-07-14de
dc.date.available2016-03-31T07:58:57Z-
dc.date.issued2010de
dc.identifier.other329965328de
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:bsz:93-opus-55093de
dc.identifier.urihttp://elib.uni-stuttgart.de/handle/11682/2690-
dc.identifier.urihttp://dx.doi.org/10.18419/opus-2673-
dc.description.abstractThe hairpin completion is a natural operation on formal languages which has been inspired by molecular phenomena in biology and by DNA-computing. In 2009 we presented a (polynomial time) decision algorithm to decide regularity of the hairpin completion. In this paper we provide four new results: 1.) We show that the decision problem is NL-complete. 2.) There is a polynomial time decision algorithm which runs in time O(n8), this improves our previous results, which provided O(n^{20}). 3.) For the one-sided case (which is closer to DNA computing) the time is O(n2), only. 4.) The hairpin completion of a regular language is unambiguous linear context-free. This result allows to compute the growth (generating function) of the hairpin completion and to compare it with the growth of the underlying regular language.en
dc.language.isoende
dc.relation.ispartofseriesTechnischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,4de
dc.rightsinfo:eu-repo/semantics/openAccessde
dc.subject.classificationEndlicher Automat , Formale Sprachede
dc.subject.ddc004de
dc.subject.otherDNA-Computing , Hairpin Completionen
dc.titleComplexity results and the growths of hairpin completions of regular languagesen
dc.typeworkingPaperde
dc.date.updated2013-07-16de
ubs.fakultaetFakultät Informatik, Elektrotechnik und Informationstechnikde
ubs.institutInstitut für Formale Methoden der Informatikde
ubs.opusid5509de
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_04.pdf403,41 kBAdobe PDFView/Open


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