@InProceedings{	  KariKS12,
  author	= "Lila Kari and Steffen Kopecki and Shinnosuke Seki",
  title		= "Iterated Hairpin Completions of Non-crossing Words",
  booktitle	= "38th Conference on Current Trends in Theory and Practice
		  of Computer Science (SOFSEM), 2011",
  editor	= "M{\'a}ria Bielikov{\'a} and Gerhard Friedrich and Georg
		  Gottlob and Stefan Katzenbeisser and Gy{\"o}rgy Tur{\'a}n",
  publisher	= "Springer",
  series	= "Lecture Notes in Computer Science",
  volume	= "7147",
  year		= "2012",
  pages		= "337--348",
  crossref	= "DBLP:conf/sofsem/2012",
  bibsource	= "DBLP, http://dblp.uni-trier.de",
  abstract	= "Iterated hairpin completion is an operation on formal
		  languages that is inspired by the hairpin formation in DNA
		  biochemistry. Iterated hairpin completion of a word (or
		  more precisely a singleton language) is always a
		  context-sensitive language and for some words it is known
		  to be non-context-free. However, it is unknown whether
		  regularity of iterated hairpin completion of a given word
		  is decidable. Also the question whether iterated hairpin
		  completion of a word can be context-free but not regular
		  was asked in literature. In this paper we investigate
		  iterated hairpin completions of non-crossing words and,
		  within this setting, we are able to answer both questions.
		  For non-crossing words we prove that the regularity of
		  iterated hairpin completions is decidable and that if
		  iterated hairpin completion of a non-crossing word is not
		  regular, then it is not context-free either.",
  doi		= "10.1007/978-3-642-27660-6_28"
}