Language-theoretic aspects of DNA complematarity

The optimism about the possibilities of DNA computing is based on two centr al issues: the Watson-Crick complementarity and the massive parallelism of DNA strands. While the latter issue renders exhaustive searches possible an d thus may settle problems previously considered intractable, the former is sue is the cause behind the universality of many models of DNA computing. M oreover, complementarity can be viewed as a purely language-theoretic opera tion: undesirable circumstances in a string trigger a transition to the com plementary string. This aspect of complementarity is investigated in the pr esent paper, mainly from the point of view of L systems. New types of word sequences will be discovered. Sometimes the resulting decision problems are equivalent to well-known open problems from other areas. (C) 2001 Elsevier Science B.V. All rights reserved.