计算机科学

计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 38-42.doi: 10.11896/jsjkx.191100204

• 理论计算机科学 • 上一篇    下一篇

带膜分裂和促进剂的通讯膜系统求解QSAT问题

宋勃升, 程玉   

  1. 湖南大学信息科学与工程学院 长沙410082
  • 收稿日期:2019-11-28 出版日期:2020-05-15 发布日期:2020-05-19
  • 通讯作者: 宋勃升(boshengsong@hnu.edu.cn)
  • 基金资助:
    国家自然科学基金(61972138,61602192);中央高校基本科研业务费(531118010355)

Uniform Solution to QAST Problem by Communication P Systems with MembraneDivision and Promoters

SONG Bo-sheng, CHENG Yu   

  1. College of Information Science and Engineering,Hunan University,Changsha 410082,China
  • Received:2019-11-28 Online:2020-05-15 Published:2020-05-19
  • About author:SONG Bo-sheng,born in 1986,Ph.D,associate professor,is a member of China Computer Federation.His main research interests include bio-inspired computing,computational intelligence and GNN.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61972138,61602192) and Fundamental Research Funds for the Central Universities (531118010355)

PDF (PC)

397

摘要： 膜计算是自然计算的一个分支,膜计算中所研究的模型均称为膜系统,而细胞间通讯是膜系统的一个重要特征。带膜分裂的通讯膜系统是一种分布式并行计算模型,可以在多项式时间内解决计算困难问题。文中将促进剂引入带膜分裂的类细胞型通讯膜系统,提出了膜系统的一种变型——带膜分裂和促进剂的通讯膜系统,其中,一个促进剂可以同时控制多条规则,而促进剂本身不参与该条规则的进化。文中研究了带膜分裂和促进剂的通讯膜系统的计算效率,证明该类膜系统在使用同向规则长度为2,每条规则中促进剂的个数最多为1时,可以在多项式时间内求解PSPACE完全问题(QSAT问题)的统一解。

关键词: 膜计算, 细胞型P系统, 同向/反向规则, QSAT问题

Abstract: Membrane computing is a branch of natural computing,and all the computing models investigated in membrane computing are called membrane systems.Communication in cells is a significant characteristic of membrane systems.Communication P systems with membrane division are distributed parallel computing models,which can solve hard computational problems in polynomial time.In this work,promoters are introduced into communication P systems with membrane division,and a variant of P systems,called communication P systems with membrane division and promoters is proposed,where any number of rules can be guided by a promoter in one step,and promoters do not participate the evolution process when the evolved rules are used.The computational efficiency of this kind of P systems is studied.This paper presents a uniform solution to the PSPACE-complete problem QSAT by using symport rules of length at most 2 and promoters of length at most 1 in a polynomial time.

Key words: Membrane computing, Cell-like P system, Symport/antiport rule, QSAT problem

中图分类号: 

  • TP301
[1] PÅUN G H.Computing with Membranes [J].J.Comput.Syst.Sci.,2000,61(1):108-143.
[2] AMAN B,CIOBANU G.Efficiently Solving The Bin PackingProblem Through Bio-Inspired Mobility [J].Acta Inform.,2017,54(4):435-445.
[3] SONG B,ZHANG C,PAN L.Tissue-Like P Systems with Evolutional Symport/Antiport Rules [J].Inf.Sci.,2017,378:177-193.
[4] DÍAZ-PERNIL M A,PEÑA-CANTILLANA F,GUTIÉRREZ-NARANJOMA.AParallel Algorithm forSkeletonizing Images by Using Spiking Neural P Systems [J].Neurocomputing,2013,115:81-91.
[5] PENG H,WANG J,PÉREZ-JIMÉNEZ M J,et al.Fuzzy Reasoning Spiking Neural P System for Fault Diagnosis [J].Inf.Sci.,2013,235:106-116.
[6] PÅUN G H.Membrane Computing.An Introduction [M].Berlin:Springer-Verlag,2000.
[7] PÅUN G H,ROZENBERG G,SALOMAA A.The OxfordHandbook of Membrane Computing [M].New York:Oxford University Press,2010.
[8] MATÍN-VIDE C,PAZOS J,PÅUN G H,et al.Tissue P Systems [J].Theor.Comput.Sci.,2003,296(2):295-326.
[9] IONESCU M,PÅUN G H,YOKOMORI T.Spiking Neural P Systems [J].Fund.Informa.,2006,71(2/3):279-308.
[10] PÅUN A,PÅUN G H.The Power of Communication:P Systems with Symport/Antiport [J].New Generat.Comput.,2002,20(3):295-305.
[11] ALHAZOV A,FREUND R.P Systems with One Membrane and Symport/Antiport Rules of Five Symbols Are Computationally Complete [C]// Proceedings of the Third Brainstor-ming Week on Membrane Computing.Sevilla:Fénix Editora,2005:19-28.
[12] ALHAZOV A,ROGOZHIN Y U.Towards A Characterization of P Systems with Minimal Symport/Antiport and Two Membranes [J].Lect.Notes.Comput.Sc.,2006,4361:135-153.
[13] BERNARDINI F,GHEORGHE M.On the Power of Minimal Symport/Antiport [C]// Proceedings of the Third Workshop on Membrane Computing.Tarragona:Fénix Editora,2003:72-83.
[14] CIOBANU G,PAN L,PÅUN G H,et al.P Systems with Minimal Parallelism [J].Theor.Comput.Sci.,2007,378:117-130.
[15] MACÍAS-ROMOS L F,SONG B,PAN L,et al.Membrane Fission:A Computational Complexity Perspective [J].Complexity,2016,21(6):321-334.
[16] SONG B,PÉREZ-JIMÉNEZ M J,PAN L.Efficient Solutions to Hard Computational Problems by P Systems with Symport/An-tiport Rules and Membrane Division [J].BioSystems,2015,130:51-58.
[17] BOTTONI P,MARTÍN-VIDE C,PÅUN G H,et al.Membrane Systems with Promoters/Inhibitors [J].Acta Inform.,2002,38:695-720.
[18] ARDELEAN I,DÍAZ-PERNIL D,GUTIÉRREZ-NARANJO M A,et al.Counting Cells with Tissue-Like P Systems [C]// Proceedings of the Tenth Brainstorming Week On Membrane Computing.Sevilla:Miguel Fénix Editora,2012:69-78.
[19] REINA-MOLINA R,DÍAZ-PERNIL D,GUTIÉRREZ-NAR-ANJO M A.Cell Complexes and Membrane Computing for Thinning 2D and 3D Images [C]// Proceedings of the Tenth Brainstorming Week On Membrane Computing.Sevilla:Fénix Editora,2012:167-186.
[20] SONG B,PAN L.The Computational Power of Tissue-Like P Systems with Promoters [J].Theor.Comput.Sci.,2016,641:43-52.
[21] ROZENBERG G,SALOMAA A.Handbook of Formal Languages [M].Berlin:Springer-Verlag,1997.
[22] PAPADIMITRIOU C H.Computational Complexity [M].Addison Wesley Publishing Company,1994.
[23] PAN L,SONG B,VALENCIA-CABRERA L,et al.The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules [J].Complexity,2018,3745210:1-22.
[24] PAN L,PÅUN G H,SONG B.Flat Maximal Parallelism in P Systems with Promoters [J].Theor.Comput.Sci.,2016,623:83-91.
[25] SONG B,PÉREZ-JIMÉNEZ M J,PAN L.An Efficient Time-Free Solution to QSAT Problem Using P Systems with Proteins on Membranes [J].Inform.Comput.,2017,256:287-299.
[26] SONG B,PÉREZ-JIMÉNEZ M J,PÅUN G H,et al.Tissue P Systems with Channel States Working in the Flat Maximally Parallel Way [J].IEEE T.Nanobiosci.,2016,15(7):645-656.
[1] 朱凯, 毋国庆, 袁梦霆. 关于同步部分规约的有限自动机的优化问题的近似难度[J]. 计算机科学, 2020, 47(5): 14-21.
[2] 寇光杰,马云艳,岳峻,邹海林. 仿生自然计算研究综述[J]. 计算机科学, 2014, 41(Z6): 37-41.
[3] 寇光杰,马云艳,岳峻,邹海林. 膜计算在图像处理中应用的研究进展及展望[J]. 计算机科学, 2014, 41(Z11): 139-143.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发