@Article{	  DieKop11,
  author	= "Volker Diekert and Steffen Kopecki",
  title		= "It is {NL}-Complete to Decide Whether a Hairpin Completion
		  of Regular Languages is Regular",
  journal	= "International Journal of Foundations of Computer Science
		  (IJFCS)",
  volume	= "22",
  number	= "8",
  year		= "2011",
  pages		= "1813--1828",
  abstract	= "The hairpin completion is an operation on formal languages
		  which is inspired by the hairpin formation in biochemistry.
		  Hairpin formations occur naturally within DNA-computing. It
		  has been known that the hairpin completion of a regular
		  language is linear context-free, but not regular, in
		  general. However, for some time it is was open whether the
		  regularity of the hairpin completion of a regular language
		  is decidable. In 2009 this decidability problem has been
		  solved positively in [5] by providing a polynomial time
		  algorithm. In this paper we improve the complexity bound by
		  showing that the decision problem is actually NL-complete.
		  This complexity bound holds for both, the one-sided and the
		  two-sided hairpin completions.",
  keywords	= "Automata and formal languages; regular languages; finite
		  automata; NL-complete problems; DNA-computing; hairpin
		  completion",
  doi		= "10.1142/S0129054111009057"
}