Affiliations: Department of Computer Science, University of Western Ontario, London, Ontario, N6A 5B7, Canada. {lila, sseki}@csd.uwo.ca; sseki@pharm.kyoto-u.ac.jp | Institute for Formal Methods in Computer Science (FMI), University of Stuttgart, Universitätsstraße, D-70569, Stuttgart, Germany. kopecki@fmi.uni-stuttgart.de
Note: [] Address for correspondence: Department of Systems Biosciences for Drug Discovery, Kyoto University, 46-29, Yoshida-Shimo-Adachi-cho, Sakyo-ku, Kyoto, 606-8501, Japan
Abstract: Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xαy\bar{α}, and outputs w' = xαy\bar{α}\bar{x}, where \bar{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 \bar{α} 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 \bar{α}, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of α and \bar{α}, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.
Keywords: combinatorics on words, commutativity of words, DNA computing, iterated hairpin completion, regularity test, single-primer hairpin completion
