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

doi:10.11896/jsjkx.191100204

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

所属专题：理论计算机科学

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

宋勃升, 程玉

湖南大学信息科学与工程学院长沙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

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)

摘要/Abstract

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

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

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: Cell-like P system, Membrane computing, QSAT problem, Symport/antiport rule

中图分类号:

TP301

宋勃升, 程玉. 带膜分裂和促进剂的通讯膜系统求解QSAT问题[J]. 计算机科学, 2020, 47(5): 38-42. https://doi.org/10.11896/jsjkx.191100204

SONG Bo-sheng, CHENG Yu. Uniform Solution to QAST Problem by Communication P Systems with MembraneDivision and Promoters[J]. Computer Science, 2020, 47(5): 38-42. https://doi.org/10.11896/jsjkx.191100204

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

Metrics

本文评价

推荐阅读 0

[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.