{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T12:34:08Z","timestamp":1774355648700,"version":"3.50.1"},"reference-count":45,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2018,4,23]],"date-time":"2018-04-23T00:00:00Z","timestamp":1524441600000},"content-version":"vor","delay-in-days":112,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61602192"],"award-info":[{"award-number":["61602192"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772214"],"award-info":[{"award-number":["61772214"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61320106005"],"award-info":[{"award-number":["61320106005"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61033003"],"award-info":[{"award-number":["61033003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2016M600592"],"award-info":[{"award-number":["2016M600592"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002858","name":"China Postdoctoral Science Foundation","doi-asserted-by":"publisher","award":["2017T100554"],"award-info":[{"award-number":["2017T100554"]}],"id":[{"id":"10.13039\/501100002858","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Tissue P systems with evolutional communication (symport\/antiport) rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in class<jats:bold>P<\/jats:bold>can be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most (<jats:italic>n<\/jats:italic>, 1), for each natural number<jats:italic>n<\/jats:italic>\u2265 1. In the case where that length is upper bounded by (3,2), a polynomial time solution to the<jats:styled-content>SAT<\/jats:styled-content>problem is provided, hence, assuming that<jats:bold>P<\/jats:bold>\u2260<jats:bold>N<\/jats:bold><jats:bold>P<\/jats:bold>a new boundary between tractability and<jats:bold>NP<\/jats:bold>\u2010hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the<jats:styled-content>SAT<\/jats:styled-content>problem.<\/jats:p>","DOI":"10.1155\/2018\/3745210","type":"journal-article","created":{"date-parts":[[2018,4,23]],"date-time":"2018-04-23T23:31:27Z","timestamp":1524526287000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["The Computational Complexity of Tissue P Systems with Evolutional Symport\/Antiport Rules"],"prefix":"10.1155","volume":"2018","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4554-455X","authenticated-orcid":false,"given":"Linqiang","family":"Pan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1479-5399","authenticated-orcid":false,"given":"Bosheng","family":"Song","sequence":"additional","affiliation":[]},{"given":"Luis","family":"Valencia-Cabrera","sequence":"additional","affiliation":[]},{"given":"Mario J.","family":"P\u00e9rez-Jim\u00e9nez","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2018,4,23]]},"reference":[{"key":"e_1_2_9_1_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1693"},{"key":"e_1_2_9_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-0526(199809\/10)4:1<20::AID-CPLX7>3.0.CO;2-H"},{"key":"e_1_2_9_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/1099-0526(200009\/10)6:1<38::AID-CPLX1006>3.0.CO;2-H"},{"key":"e_1_2_9_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-016-9570-5"},{"key":"e_1_2_9_5_2","first-page":"135","article-title":"Spiking neural P systems with an exhaustive use of rules","volume":"3","author":"Ionescu M.","year":"2007","journal-title":"International Journal of Unconventional Computing"},{"key":"e_1_2_9_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-005-3771-7"},{"key":"e_1_2_9_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.biosystems.2011.12.006"},{"key":"e_1_2_9_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2015.01.019"},{"key":"e_1_2_9_9_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0129065716500040"},{"key":"e_1_2_9_10_2","doi-asserted-by":"publisher","DOI":"10.1142\/s0129065714400061"},{"key":"e_1_2_9_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00659-X"},{"key":"e_1_2_9_12_2","doi-asserted-by":"crossref","first-page":"279","DOI":"10.3233\/FUN-2006-712-308","article-title":"Spiking neural P systems","volume":"71","author":"Ionescu M.","year":"2006","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_9_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11467-0"},{"key":"e_1_2_9_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037362"},{"key":"e_1_2_9_15_2","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410600367X"},{"key":"e_1_2_9_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36490-0_22"},{"key":"e_1_2_9_17_2","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410200145X"},{"key":"e_1_2_9_18_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129515000018"},{"key":"e_1_2_9_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.09.013"},{"key":"e_1_2_9_20_2","first-page":"305","article-title":"Modelling grammar systems by tissue P systems working in the sequential mode","volume":"76","author":"Freund R.","year":"2007","journal-title":"Fundamenta Informaticae"},{"key":"e_1_2_9_21_2","doi-asserted-by":"publisher","DOI":"10.15837\/ijccc.2008.3.2397"},{"key":"e_1_2_9_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-016-0264-3"},{"key":"e_1_2_9_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73053-8_17"},{"key":"e_1_2_9_24_2","first-page":"229","article-title":"Computational efficiency of cellular division in tissue-like membrane systems","volume":"11","author":"D\u00edaz-Pernil D.","year":"2008","journal-title":"Romanian Journal of Information, Science and Technology"},{"key":"e_1_2_9_25_2","first-page":"89","article-title":"A P-Lingua based simulator for tissue P systems with cell separation","volume":"17","author":"P\u00e9rez-Hurtado I.","year":"2014","journal-title":"Romanian Journal of Information Science and Technology"},{"key":"e_1_2_9_26_2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2015-1197"},{"key":"e_1_2_9_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.11.015"},{"key":"e_1_2_9_28_2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2015-1201"},{"key":"e_1_2_9_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2010.03.001"},{"key":"e_1_2_9_30_2","unstructured":"PorrecaA. E. MurphyN. andP\u00e9rez-Jim\u00e9nezM. J. An optimal frontier of the efficiency of tissue P systems with cell division Proceedings of the Tenth Brainstorming Week on Membrane Computing 2012 Seville Spain 141\u2013166."},{"key":"e_1_2_9_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11467-0_21"},{"key":"e_1_2_9_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/cplx.21691"},{"key":"e_1_2_9_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2016.10.046"},{"key":"e_1_2_9_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95885-7_14"},{"key":"e_1_2_9_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11467-0_20"},{"key":"e_1_2_9_36_2","unstructured":"P-Lingua http:\/\/www.p-lingua.org\/."},{"key":"e_1_2_9_37_2","doi-asserted-by":"crossref","unstructured":"P\u00e9rez-HurtadoI. Valencia-CabreraL. P\u00e9rez-Jim\u00e9nezM. J. ColomerM. A. andRiscos-N\u00fa\u00f1ezA. LiK. TangZ. LiR. NagarA. K. andThamburajR. MeCoSim: A general purpose software tool for simulating biological phenomena by means of P systems 1 Proceedings of the 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications BIC-TA 2010 September 2010 Changsha China IEEE Press 637\u2013643 https:\/\/doi.org\/10.1109\/BICTA.2010.5645199 2-s2.0-78650623142.","DOI":"10.1109\/BICTA.2010.5645199"},{"key":"e_1_2_9_38_2","unstructured":"MeCoSim http:\/\/www.p-lingua.org\/mecosim\/."},{"key":"e_1_2_9_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"e_1_2_9_40_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1025449224520"},{"key":"e_1_2_9_41_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_9_42_2","unstructured":"PanL. P\u00e9rez-Jim\u00e9nezM. J. Riscos-N\u00fa\u00f1ezA. andRius-FontM. New frontiers of the efficiency in tissue P systems Proceedings of the Asian Conference on Membrane Computing 2012 Wuhan China 61\u201373."},{"key":"e_1_2_9_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36751-9_17"},{"key":"e_1_2_9_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.10.027"},{"key":"e_1_2_9_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNB.2016.2594380"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2018\/3745210.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2018\/3745210.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2018\/3745210","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T22:02:22Z","timestamp":1751580142000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2018\/3745210"}},"subtitle":[],"editor":[{"given":"Sigurdur F.","family":"Hafstein","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1155\/2018\/3745210"],"URL":"https:\/\/doi.org\/10.1155\/2018\/3745210","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"value":"1076-2787","type":"print"},{"value":"1099-0526","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]},"assertion":[{"value":"2017-05-29","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-12-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-04-23","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"3745210"}}