计算机科学 ›› 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] | 朱凯, 毋国庆, 袁梦霆. 关于同步部分规约的有限自动机的优化问题的近似难度[J]. 计算机科学, 2020, 47(5): 14-21. |
[2] | 寇光杰,马云艳,岳峻,邹海林. 仿生自然计算研究综述[J]. 计算机科学, 2014, 41(Z6): 37-41. |
[3] | 寇光杰,马云艳,岳峻,邹海林. 膜计算在图像处理中应用的研究进展及展望[J]. 计算机科学, 2014, 41(Z11): 139-143. |
|