系统工程理论与实践
繫統工程理論與實踐
계통공정이론여실천
SYSTEMS ENGINEERING--THEORY & PRACTICE
2013年
9期
2362-2370
,共9页
谭钢军%宋勃升%陈智华%石晓龙
譚鋼軍%宋勃升%陳智華%石曉龍
담강군%송발승%진지화%석효룡
膜计算%插入-删除系统%插入-删除膜系统%通用性
膜計算%插入-刪除繫統%插入-刪除膜繫統%通用性
막계산%삽입-산제계통%삽입-산제막계통%통용성
membrane computing%insertion-deletion system%insertion-deletion P system%universality
插入-删除系统是一类受生物过程中错配退火的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]中提齣的公開問題.
삽입-산제계통시일류수생물과정중착배퇴화적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]중제출적공개문제.
