计算机科学 ›› 2020, Vol. 47 ›› Issue (5): 38-42.doi: 10.11896/jsjkx.191100204
所属专题: 理论计算机科学
宋勃升, 程玉
SONG Bo-sheng, CHENG Yu
摘要: 膜计算是自然计算的一个分支,膜计算中所研究的模型均称为膜系统,而细胞间通讯是膜系统的一个重要特征。带膜分裂的通讯膜系统是一种分布式并行计算模型,可以在多项式时间内解决计算困难问题。文中将促进剂引入带膜分裂的类细胞型通讯膜系统,提出了膜系统的一种变型——带膜分裂和促进剂的通讯膜系统,其中,一个促进剂可以同时控制多条规则,而促进剂本身不参与该条规则的进化。文中研究了带膜分裂和促进剂的通讯膜系统的计算效率,证明该类膜系统在使用同向规则长度为2,每条规则中促进剂的个数最多为1时,可以在多项式时间内求解PSPACE完全问题(QSAT问题)的统一解。
中图分类号:
[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] | 张露萍, 徐飞. 具有突触规则的脉冲神经膜系统综述 Survey on Spiking Neural P Systems with Rules on Synapses 计算机科学, 2022, 49(8): 217-224. https://doi.org/10.11896/jsjkx.220300078 |
[2] | 殷秀, 刘希林, 刘希玉. 具有多个突触通道的新型数值脉冲神经P系统的计算能力研究 Study on Computing Capacity of Novel Numerical Spiking Neural P Systems with MultipleSynaptic Channels 计算机科学, 2022, 49(6A): 223-231. https://doi.org/10.11896/jsjkx.210200171 |
[3] | 朱凯, 毋国庆, 袁梦霆. 关于同步部分规约的有限自动机的优化问题的近似难度 On Hardness of Approximation for Optimized Problem of Synchronizing Partially Specified Deterministic Finite Automata 计算机科学, 2020, 47(5): 14-21. https://doi.org/10.11896/jsjkx.200200073 |
[4] | 寇光杰,马云艳,岳峻,邹海林. 仿生自然计算研究综述 Survey of Bio-inspired Natural Computing 计算机科学, 2014, 41(Z6): 37-41. |
[5] | 寇光杰,马云艳,岳峻,邹海林. 膜计算在图像处理中应用的研究进展及展望 Research Advance and Prospect of Membrane Computing Applied in Image Processing 计算机科学, 2014, 41(Z11): 139-143. |
|