Deciding regularity of hairpin completions of regular languages in polynomial time

AbstractHairpin completion is an operation on formal languages that has been inspired by hairpin formation in DNA biochemistry and by DNA computing. In this paper we investigate the one- and two-sided hairpin completion of regular languages. We solve an open problem from the literature by showing that the regularity problem for hairpin completions is decidable. Actually, we show that the problem is decidable in polynomial time if the input is specified by DFAs.Furthermore, we prove that the hairpin completion of regular languages is an unambiguous linear context-free language. Beforehand, it was known only that it is linear context-free. Unambiguity is a strong additional property because it allows to compute the growth function or the topological entropy. In particular, we can compare the growth of the hairpin completion with the growth of the defining regular languages. We show that the growth of the hairpin completion is exponential if and only if the growth of the underlying languages is exponential. Even if both growth functions are exponential, they can be as far apart as 2Θ(n) for the hairpin completion and 2Θ(n) for the defining regular languages. However, if the hairpin completion is still regular, then the hairpin completion and its underlying language have essentially the same growth and same topological entropy