At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems
At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems
复制标题
在 DNA 计算和形式语言的十字路口：使用插入删除系统表征递归可枚举语言
DOI：
10.1090/dimacs/048/23
复制
发表时间：
1997
影响因子：
3.5
通讯作者：
Sheng Yu
中科院分区：
文献类型：
--
作者：
L. Kari;G. Paun;G. Thierrin;Sheng Yu
使用插入删除系统提出了递归可枚举（RE）语言的几个特征。这样的系统通过根据上下文插入和删除单词来生成语言元素（插入删除规则是三元组（u，z，v），意味着z可以在上下文（u，v）中插入或删除）。基于插入规则的语法已经在[10]中考虑了语言动机。插入/删除操作也是 DNA 和 RNA 处理的基础[5]。我们的结果表明，即使对上下文的长度和/或插入/删除的单词的长度或形式有严格的限制，这些操作在计算上也是完整的，也就是说，它们可以模拟任何图灵机的工作。 [30]中提出的问题在这种情况下得到解决。
Several characterizations of recursively enumerable (RE) languages are presented, using insertion-deletion systems. Such a system generates the elements of a language by inserting and deleting words, according to their contexts (the insertion-deletion rules are triples (u, z, v), with the meaning that z can be inserted or deleted in/from the context (u, v)). Grammars based on insertion rules have already been considered in [10] with linguistic motivation. Insertion/deletion operations are also basic in DNA and RNA processing,[5]. Our results show that these operations, even with strong restrictions on the length of the contexts and/or on the length or on the form of the inserted/deleted words are computationally complete, that is, they can simulate the work of any Turing machine. A problem formulated in [30] is solved in this context.