Freund R, Păun G, Rozenberg G, Salomaa A
Department of Computer Science, Vienna University of Technology, Wien, Austria.
Pac Symp Biocomput. 1998:535-46.
We introduce two-sided sticker systems, the two-sided variant of a computability model introduced as an abstraction of Adleman's style of DNA computing and of the matching of the so-called Watson-Crick complements. Several types of sticker systems are shown to have the same power as regular grammars, one variant is found to represent the linear languages, and another one is proved to be able to represent any recursively enumerable language. From this result we infer that any recursively enumerable language can be represented as the projection of the intersection of two minimal linear languages.
我们引入了双面粘贴系统，它是一种可计算性模型的双面变体，该模型作为阿德尔曼式DNA计算风格以及所谓沃森-克里克互补配对的抽象而引入。已证明几种类型的粘贴系统与正则文法具有相同的能力，发现一种变体可表示线性语言，另一种则被证明能够表示任何递归可枚举语言。从这个结果我们推断，任何递归可枚举语言都可以表示为两个最小线性语言交集的投影。
