Deciding Regularity of Hairpin Completions of Regular Languages in Polynomial Time

Volker Diekert, Steffen Kopecki, Victor Mitrana

The hairpin completion is an operation on formal languages that has been inspired by the hairpin formation in DNA biochemistry and by DNA computing. In this paper we investigate th…