Paper Info
Title
Bond-free languages: formalizations, maximality and construction methods
Abstract
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.
Year
DOI
Venue
2004
10.1007/11493785_15
DNA'04 Proceedings of the 10th international conference on DNA computing
Keywords
Field
DocType
polynomial-time decidable,regular language,k-code property,Hamming similarity,maximal Hamming bond-free language,DNA computation,DNA language,bond-free language,construction method,similarity relation,Bond-free language
Hamming code,Discrete mathematics,Combinatorics,Abstract family of languages,Decidability,Cone (formal languages),Regular language,Pumping lemma for regular languages,Mathematics,DNA computing,Ontology language
Conference
Volume
Issue
ISSN
16
5
0129-0541
ISBN
Citations 
PageRank 
3-540-26174-5
0
0.34
References 
Authors
0
3
Name
Order
Citations
PageRank
Lila Kari11123124.45
Stavros Konstantinidis228331.10
Petr Sosík347968.66