Diekert, VolkerKopecki, Steffen2010-07-142016-03-312010-07-142016-03-312010329965328http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-55093http://elib.uni-stuttgart.de/handle/11682/2690http://dx.doi.org/10.18419/opus-2673The 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.eninfo:eu-repo/semantics/openAccessEndlicher Automat , Formale Sprache004DNA-Computing , Hairpin CompletionworkingPaper2013-07-16