Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2673
Langanzeige der Metadaten
DC Element | Wert | Sprache |
---|---|---|
dc.contributor.author | Diekert, Volker | de |
dc.contributor.author | Kopecki, Steffen | de |
dc.date.accessioned | 2010-07-14 | de |
dc.date.accessioned | 2016-03-31T07:58:57Z | - |
dc.date.available | 2010-07-14 | de |
dc.date.available | 2016-03-31T07:58:57Z | - |
dc.date.issued | 2010 | de |
dc.identifier.other | 329965328 | de |
dc.identifier.uri | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-55093 | de |
dc.identifier.uri | http://elib.uni-stuttgart.de/handle/11682/2690 | - |
dc.identifier.uri | http://dx.doi.org/10.18419/opus-2673 | - |
dc.description.abstract | The 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.iso | en | de |
dc.relation.ispartofseries | Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2010,4 | de |
dc.rights | info:eu-repo/semantics/openAccess | de |
dc.subject.classification | Endlicher Automat , Formale Sprache | de |
dc.subject.ddc | 004 | de |
dc.subject.other | DNA-Computing , Hairpin Completion | en |
dc.title | Complexity results and the growths of hairpin completions of regular languages | en |
dc.type | workingPaper | de |
dc.date.updated | 2013-07-16 | de |
ubs.fakultaet | Fakultät Informatik, Elektrotechnik und Informationstechnik | de |
ubs.institut | Institut für Formale Methoden der Informatik | de |
ubs.opusid | 5509 | de |
ubs.publikation.typ | Arbeitspapier | de |
ubs.schriftenreihe.name | Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik | de |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
TR_2010_04.pdf | 403,41 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.