Two Operations Suggested by DNA Biochemistry: Hairpin Completion and Superposition
Prof. Dr. Victor Mitrana
(Faculty of Mathematics and Computer Science, Univ. of Bucharest and
Department of Information Systems and Computation, Technical University of Valencia)

Place: Room 0S03 (Ground floor at the DSIC building in front of Secretariat)
Date: 04/12/2008
Time: 12:30
Abstract

We propose two new formal operations on words and languages suggested by DNA manipulation, called superposition and hairpin completion. By these operations, that are based on the Watson-Crick complementarity, annealing and PCR, one can generate a set of words, starting from a pair of words or a single word, respectively. These operations are considered here as abstract operations on formal languages. We settle the closure properties under the non-iterated version of these operations of some classes in the Chomsky hierarchy as well as some complexity classes.
The iterated version of each of the two operations is then discussed. We propose an O(n²f(n)) time recognition algorithm for the iterated hairpin completion of a language recognizable in O(f(n)) time. The n² factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. Similar results are obtained for the iterated superposition. We then define two distances and present polynomial time algorithms for computing them. Finally, we give a short list of open problems which appear attractive to us.