Bond-free Languages: Formalizations, Maximality and Construction Methods

	L. Kari, S. Konstantinidis, Petr Sos\'\i k

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 $\rsim$-bond-freedom, where $\rsim$ 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
$\theta$-$k$-code property introduced by Jonoska and Mahalingam.