2011/04/13 by Lila Kari, Kari, Lila, Steffen Kopecki +3
Computer Science · #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #cs.FL
paper · pdf · doi:10.48550/arxiv.1104.2385
17 pages, 1 figure, submitted to Fundamenta Informaticae
arxiv created 2011/04/13 · arxiv updated 2011/04/14
Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xαy \calpha, and outputs w' = x αy α x, where x denotes the Watson-Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words α and \calpha that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of α and \calpha, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of α and \calpha, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.