{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:27:28Z","timestamp":1762504048967,"version":"build-2065373602"},"reference-count":24,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","funder":[{"name":"FEDER\/Junta de Andalucia \u2013 Paidi 2020\/_Proyecto","award":["P20_00486"],"award-info":[{"award-number":["P20_00486"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:p>In the framework of membrane computing, several interesting results concerning frontiers of efficiency between the complexity classes P and NP have been found by using different ingredients. One of the main characteristics of cell-like membrane systems is their rooted tree-like structure, where a natural parent-children membrane relationship exists, and objects can travel through the membranes. Separation rules are used as a method to obtain an exponential workspace in terms of membranes in polynomial time. Inspired by cell meiosis, objects from the original membrane are distributed between the two new membranes. In this work, P systems with evolutional symport\/antiport rules and separation rules are used to give a solution to SAT, a well known NP-complete problem. One of the advantages of this solution is the use of the environment as a passive agent.<\/jats:p>","DOI":"10.1142\/s0129054123450065","type":"journal-article","created":{"date-parts":[[2023,9,29]],"date-time":"2023-09-29T02:42:01Z","timestamp":1695955321000},"page":"1089-1116","source":"Crossref","is-referenced-by-count":0,"title":["A Formal Verification of a SAT Solution by P Systems with Evolution Communication and Separation Rules"],"prefix":"10.1142","volume":"36","author":[{"given":"David","family":"Orellana-Mart\u00edn","sequence":"first","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012, Sevilla, Spain"},{"name":"SCORE Laboratory, I3US, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012, Sevilla, Spain"}]},{"given":"Luis","family":"Valencia-Cabrera","sequence":"additional","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012, Sevilla, Spain"},{"name":"SCORE Laboratory, I3US, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012, Sevilla, Spain"}]},{"given":"Mario J.","family":"P\u00e9rez-Jim\u00e9nez","sequence":"additional","affiliation":[{"name":"Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012, Sevilla, Spain"},{"name":"SCORE Laboratory, I3US, Universidad de Sevilla, Avda. Reina Mercedes s\/n, 41012, Sevilla, Spain"}]}],"member":"219","published-online":{"date-parts":[[2023,9,29]]},"reference":[{"key":"S0129054123450065BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18123-8_9"},{"key":"S0129054123450065BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2021.104766"},{"key":"S0129054123450065BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.12.094"},{"key":"S0129054123450065BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77312-2_14"},{"key":"S0129054123450065BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.09.013"},{"key":"S0129054123450065BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-28475-0_10"},{"key":"S0129054123450065BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54239-8_1"},{"key":"S0129054123450065BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfranklin.2022.02.017"},{"issue":"1","key":"S0129054123450065BIB009","first-page":"53","volume":"15","author":"Krishna S. N.","year":"2001","journal-title":"Acta Cybern"},{"key":"S0129054123450065BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00659-X"},{"key":"S0129054123450065BIB011","doi-asserted-by":"publisher","DOI":"10.1155\/2021\/7120840"},{"key":"S0129054123450065BIB012","doi-asserted-by":"publisher","DOI":"10.3390\/axioms10040327"},{"key":"S0129054123450065BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-13502-6_10"},{"issue":"5","key":"S0129054123450065BIB015","first-page":"630","volume":"10","author":"Pan L.","year":"2004","journal-title":"J. Univers. Comput. Sci."},{"key":"S0129054123450065BIB016","doi-asserted-by":"publisher","DOI":"10.1155\/2018\/3745210"},{"key":"S0129054123450065BIB017","first-page":"1331","volume-title":"2010 IEEE Fifth International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA)","author":"Pavel A.","year":"2010"},{"key":"S0129054123450065BIB018","first-page":"75","volume":"6","author":"P\u0103un Gh.","year":"1999","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S0129054123450065BIB019","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1693"},{"key":"S0129054123450065BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56196-2"},{"key":"S0129054123450065BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11467-0"},{"key":"S0129054123450065BIB022","doi-asserted-by":"publisher","DOI":"10.1080\/00207160.2012.748898"},{"key":"S0129054123450065BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6"},{"key":"S0129054123450065BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2016.10.046"},{"key":"S0129054123450065BIB025","doi-asserted-by":"publisher","DOI":"10.1063\/5.0027078"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123450065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:17:00Z","timestamp":1762503420000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123450065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,29]]},"references-count":24,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["10.1142\/S0129054123450065"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123450065","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,9,29]]}}}