Hairpin languages

Gheorghe Pǎun, Grzegorz Rozenberg, Takashi Yokomori

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)


Molecules with hairpin structure(s) form a natural extension of linear non-branched molecules, and they have been already used in experimental work in DNA computing. In this paper we introduce and investigate classes of string languages (hence languages modeling the sets of linear DNA molecules), consisting of strings which can (fold on itself and) form hairpins. We classify the complexity of these classes using language-theoretic techniques. We also discuss a further use of hairpin molecules in DNA computing.

Original languageEnglish
Pages (from-to)837-847
Number of pages11
JournalInternational Journal of Foundations of Computer Science
Issue number6
Publication statusPublished - 2001

ASJC Scopus subject areas

  • Computer Science (miscellaneous)


Dive into the research topics of 'Hairpin languages'. Together they form a unique fingerprint.

Cite this