Some remarks on the hairpin completion

Florin Manea*, Victor Mitrana, Takashi Yokomori

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


We consider several problems regarding the iterated or non-iterated hairpin completion of some subclasses of regular languages. Thus we obtain a characterization of the class of regular languages as the weak-code images of the k-hairpin completion of center-disjoint k-locally testable languages in the strict sense. This result completes two results from [3] and [11]. Then we investigate some decision problems and closure properties of the family of the iterated hairpin completion of singleton languages. Finally, we discuss some algorithms regarding the possibility of computing the values of k such that the non-iterated or iterated k-hairpin completion of a given regular language does not produce new words.

Original languageEnglish
Pages (from-to)859-872
Number of pages14
JournalInternational Journal of Foundations of Computer Science
Issue number5
Publication statusPublished - 2010 Oct
Externally publishedYes


  • DNA computing
  • hairpin completion
  • regular languages

ASJC Scopus subject areas

  • Computer Science (miscellaneous)


Dive into the research topics of 'Some remarks on the hairpin completion'. Together they form a unique fingerprint.

Cite this