Narrow Results

The problem of negative design of DNA languages is addressed, that is, properties and construction methods of large sets of words that prevent undesired bonds when used in DNA computations. We recall a few existing formalizations of the problem and then define the property of sim-bond-freedom, where sim is a similarity relation between words. We show that this property is decidable for context-free languages and polynomial-time decidable for regular languages. The maximality of this property also turns out to be decidable for regular languages and polynomial-time decidable for an important case of the Hamming similarity. Then we consider various construction methods for Hamming bond-free languages, including the recently introduced method of templates, and obtain a complete structural characterization of all maximal Hamming bond-free languages. This result is applicable to the θ-k-code property introduced by Jonoska and Mahalingam.

We are interested in the state complexity of languages that are defined via the subword closure operation. The subword closure of a set S of fixed-length words is the set of all words w for which any subword of w of the fixed length is in S. This type of constraint appears to be useful in various situations related to data encodings and in particular to DNA encodings. We present a few results related to this concept. In particular we give a general upper bound on the state complexity of a subword closed language and show that this bound is tight infinitely often. We also discuss the state complexity of DNA computing related cases of the subword closure operation.