2011/08/11 by Volker Diekert, Diekert, Volker, Steffen Kopecki +4
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced biosensing and bioanalysis techniques #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1108.2427
arxiv created 2011/08/11 · openalex publication_date 2011/08/11 · arxiv updated 2011/08/12 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
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 the hairpin completion of regular languages. It is well known that hairpin completions of regular languages are linear context-free and not necessarily regular. As regularity of a (linear) context-free language is not decidable, the question arose whether regularity of a hairpin completion of regular languages is decidable. We prove that this problem is decidable and we provide a polynomial time algorithm. Furthermore, we prove that the hairpin completion of regular languages is an unambiguous linear context-free language and, as such, it has an effectively computable growth function. Moreover, we show that the growth of the hairpin completion is exponential if and only if the growth of the underlying languages is exponential and, in case the hairpin completion is regular, then the hairpin completion and the underlying languages have the same growth indicator.