@Article{	  Kopecki11,
  title		= "On iterated hairpin completion",
  journal	= "Theoretical Computer Science",
  volume	= "412",
  number	= "29",
  pages		= "3629--3638",
  year		= "2011",
  note		= "",
  issn		= "0304-3975",
  author	= "Steffen Kopecki",
  keywords	= "Bounded hairpin completion",
  abstract	= "The (bounded) hairpin completion and its iterated versions
		  are operations on formal languages which have been inspired
		  by the hairpin formation in DNA-biochemistry. The paper
		  answers two questions asked in the literature about the
		  iterated hairpin completion. The first question is whether
		  the class of regular languages is closed under iterated
		  bounded hairpin completion. Here we show that this is true
		  by providing a more general result which applies to all the
		  classes of languages which are closed under finite union,
		  intersection with regular sets, and concatenation with
		  regular sets. In particular, all Chomsky classes and all
		  standard complexity classes are closed under iterated
		  bounded hairpin completion. In the second part of the paper
		  we address the question whether the iterated hairpin
		  completion of a singleton is always regular. In contrast to
		  the first question, this one has a negative answer. We
		  exhibit an example of a singleton language whose iterated
		  hairpin completion is not regular, actually it is not
		  context-free, but context-sensitive.",
  doi		= "10.1016/j.tcs.2011.03.009"
}