Bond-Free Languages: Formalizations, Maximality and Construction Methods
Bond-Free Languages: Formalizations, Maximality and Construction Methods
复制标题
无键语言：形式化、最大化和构造方法
DOI：
10.1007/11493785_15
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Petr Sosík
中科院分区：
文献类型：
--
作者：
L. Kari;S. Konstantinidis;Petr Sosík
讨论了DNA语言的负设计问题，即在DNA计算中使用防止不需要的键的大词集的性质和构造方法。我们回顾了已有的几个问题的形式化描述，并定义了sim键自由的性质，其中sim是词之间的相似关系。我们证明了这一性质对于上下文无关语言是可判定的，对于正则语言是多项式时间可判定的。这一性质的极大性对于正则语言也是可判定的，对于Hamming相似的重要情况是多项式时间可判定的。然后，我们考虑了Hamming无键语言的各种构造方法，包括最近引入的模板法，得到了所有极大Hamming无键语言的完整结构特征。这一结果适用于由Jonoska和Mahalingam引入的θ-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 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.