单边插入-删除(膜)系统计算能力

摘要：

插入-删除系统是一类受生物过程中错配退火的DNA序列启发的计算模型.本文研究了使用单边插入规则或删除规则的插入-删除系统的计算能力.研究表明,插入1个符号(上下文参数是(2,0))并且删除2个符号(上下文参数是(0,1))的插入-删除系统是通用的;插入1个符号(上下文参数是(0,1))并且删除1个符号(上下文参数是(1,0))的插入-删除系统是不通用的;另外,本文还给出了3个通用的单边插入-删除膜系统,而在插入-删除系统中,它们是不通用的.这些结果部分回答了[Proceedings of 12th International Workshop on Descriptional Complexity of Formal Systems,2010,88-98]中提出的公开问题.

关键词：膜计算、插入-删除系统、插入-删除膜系统、通用性

所属期刊栏目：33

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61033003,91130034,61100145,61272071

在线出版日期：2013-10-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：2362-2370