2011/10/04 by Lila Kari, Kari, Lila, Steffen Kopecki +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #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.1110.0760
arxiv created 2011/10/04 · openalex publication_date 2011/10/04 · arxiv updated 2011/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Iterated hairpin completion is an operation on formal languages that is inspired by the hairpin formation in DNA biochemistry. Iterated hairpin completion of a word (or more precisely a singleton language) is always a context-sensitive language and for some words it is known to be non-context-free. However, it is unknown whether regularity of iterated hairpin completion of a given word is decidable. Also the question whether iterated hairpin completion of a word can be context-free but not regular was asked in literature. In this paper we investigate iterated hairpin completions of non-crossing words and, within this setting, we are able to answer both questions. For non-crossing words we prove that the regularity of iterated hairpin completions is decidable and that if iterated hairpin completion of a non-crossing word is not regular, then it is not context-free either.