CAJ | 학술논문

插入-删除系统是一类受生物过程中错配退火的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]中提出的公开问题.
삽입-산제계통시일류수생물과정중착배퇴화적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]중제출적공개문제.
Insertion-deletion systems are a class of computation models inspired by the biological process -- mismatched annealing of DNA sequences. In this work, we investigate the computation power of insertion-deletion systems having a context on one side of insertion or deletion rules. We prove that an insertion-deletion system which asymmetrically insert one symbol and delete two symbols is Turing universal; an insertion-deletion system which asymmetrically insert one symbol and delete one symbol is not Turing universal. Three Turing universal one-sided insertion-deletion P systems are presented, where the three corresponding one-sided insertion-deletion systems are not universal. The results partially answer open problems formulated in [Proceedings of 12th International Workshop on Descriptional Complexity of Formal Systems, 2010, 88-98].