{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T17:10:03Z","timestamp":1747847403292,"version":"3.41.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319106823"},{"type":"electronic","value":"9783319106830"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-10683-0_15","type":"book-chapter","created":{"date-parts":[[2015,3,25]],"date-time":"2015-03-25T15:54:11Z","timestamp":1427298851000},"page":"361-385","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Membrane Computing: Basics and Frontiers"],"prefix":"10.1007","author":[{"given":"Gheorghe","family":"P\u0103un","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,11]]},"reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"C.S. Calude, Gh. P\u0103un, G. Rozenberg, A. Salomaa (eds.) Multiset Processing. Mathematical, Computer Science, and Molecular Computing Points of View. LNCS, vol. 2235 (Springer, Berlin, 2001) The first international meeting devoted to membrane computing was organized already in the summer of 2000, in Curtea de Arge\u015f, Romania, and it was concerned both with the developments in the emerging research area of membrane computing and with the mathematical and computer science investigations of multisets. This LNCS volume is the proceedings of the workshop, edited after the meeting.","DOI":"10.1007\/3-540-45523-X"},{"key":"15_CR2","unstructured":"G. Ciobanu, Gh. P\u0103un, M.J. P\u00e9rez-Jim\u00e9nez (eds.) Applications of Membrane Computing (Springer, Berlin, 2006) The volume presents several classes of applications (in biology and biomedicine, computer science, linguistics), as well as the software available at the time of editing the book, and a selective bibliography of membrane computing. Here are the sections of the chapter Computer Science Applications: Static sorting P systems; Membrane-based devices used in computer graphics; An analysis of a public key protocol with membranes; Membrane algorithms: approximate algorithms for NP-complete optimization problems; and Computationally hard problems addressed through P systems."},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"P. Frisco, M. Gheorghe, M.J. P\u00e9rez-Jim\u00e9nez (eds.) Applications of Membrane Computing in Systems and Synthetic Biology. (Springer, Berlin, 2014) Different from volume [2], this time only applications in biology and biomedicine are concerned, at the level of year 2013, with a detailed biological motivation, in most cases reporting research done in interdisciplinary teams, including both biologists and computer scientists.","DOI":"10.1007\/978-3-319-03191-0"},{"key":"15_CR4","unstructured":"R. Freund, Particular results for variants of P systems with one catalyst in one membrane, in Proc. Fourth Brainstorming Week on Membrane Computing, vol. II (F\u00e9nix Editora, Sevilla, 2006), pp. 41\u201350"},{"key":"15_CR5","unstructured":"R. Freund, Purely catalytic P systems: Two catalysts can be sufficient for computational completeness, in Proc. 14th Intern. Conf. on Membrane Computing (Chi\u015fin\u0103u, Moldova, 2013), pp. 153\u2013166"},{"key":"15_CR6","unstructured":"R. Freund, O.H. Ibarra, A. P\u0103un, P. Sos\u00edk, H.-C. Yen, Catalytic P systems. Chapter\u00a04 of [30]"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"R. Freund, L. Kari, M. Oswald, P. Sos\u00edk, Computationally universal P systems without priorities: two catalysts are sufficient. Theor. Comput. Sci. 330, 251\u2013266 (2005) After a series of previous papers, the first one, by P. Sos\u00edk, where the universality of catalytic P systems was proved for systems with 8, then 6, catalysts, this paper established the best result in this respect: two catalysts suffice.","DOI":"10.1016\/j.tcs.2004.06.029"},{"key":"15_CR8","unstructured":"R. Freund, Gh. P\u0103un, Universal P systems: One catalyst can be sufficient, in Proc. 11th Brainstorming Week on Membrane Computing (F\u00e9nix Editora, Sevilla, 2013), pp. 81\u201396"},{"key":"15_CR9","unstructured":"M. Gheorghe, Gh. P\u0103un, M.J. P\u00e9rez-Jim\u00e9nez, G. Rozenberg, Frontiers of membrane computing: Open problems and research topics. Int. J. Found. Comput. Sci. 24(5), 547\u2013623 (2013) (first version in Proc. Tenth Brainstorming Week on Membrane Computing, vol.\u00a0I (Sevilla, 2012), pp. 171\u2013249, January 30\u2013February 3) This paper circulated in the membrane computing community in the brainstorming version under the title of \u201cmega-paper.\u201d In this form, it contains 26 sections, written by separate authors, covering most of the branches of this research area and presenting open problems and research topics of current interest. The titles of these 26 sections are worth recalling: A glimpse to membrane computing; Some general issues; The power of small numbers; Polymorphic P systems; P colonies and dP automata; Spiking neural P systems; Control words associated with P systems; Speeding up P automata; Space complexity and the power of elementary membrane division; The P-conjecture and hierarchies; Seeking sharper frontiers of efficiency in tissue P systems; Time-free solutions to hard computational problems; Fypercomputations; Numerical P systems; P systems formal verification and testing; Causality, semantics, behavior; Kernel P systems; Bridging P and R; P systems and evolutionary computing interactions; Metabolic P systems; Unraveling oscillating structures by means of P systems; Simulating cells using P systems; P systems for computational systems and synthetic biology; Biologically plausible applications of spiking neural P systems for an explanation of brain cognitive functions; Computer vision; and Open problems on simulation of membrane computing models."},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.tcs.2003.10.028","volume":"312","author":"O.H. Ibarra","year":"2004","unstructured":"O.H. Ibarra, Z. Dang, O. Egecioglu, Catalytic P systems, semilinear sets, and vector addition systems. Theor. Comput. Sci. 312, 379\u2013399 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"O.H. Ibarra, Z. Dang, O. Egecioglu, G. Saxena, Characterizations of catalytic membrane computing systems, in 28th Intern. Symp. Math. Found. Computer Sci., ed. by B. Rovan, P.\u00a0Vojt\u00e1s. LNCS, vol. 2747 (Springer, 2003), pp. 480\u2013489","DOI":"10.1007\/978-3-540-45138-9_42"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"M. Ionescu, Gh. P\u0103un, T. Yokomori, Spiking neural P systems. Fundamenta Informaticae 71(2\u20133), 279\u2013308 (2006) This is the paper where the spiking neural P systems were introduced, and two basic results of this area were proved: universality in the general case, and semilinearity of the computed sets of numbers in the bounded case. Similar results were later obtained for many classes of SN P systems.","DOI":"10.3233\/FUN-2006-712-308"},{"issue":"4","key":"15_CR13","doi-asserted-by":"crossref","first-page":"423","DOI":"10.3233\/FI-2011-571","volume":"11","author":"M. Ionescu","year":"2011","unstructured":"M. Ionescu, Gh. P\u0103un, M.J. P\u00e9rez-Jim\u00e9nez, T. Yokomori, Spiking neural dP systems. Fundamenta Informaticae 11(4), 423\u2013436 (2011)","journal-title":"Fundamenta Informaticae"},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1007\/BF03037288","volume":"22","author":"S.N. Krishna","year":"2004","unstructured":"S.N. Krishna, A. P\u0103un, Results on catalytic and evolution-communication P systems. New Generat. Comput. 22, 377\u2013394 (2004)","journal-title":"New Generat. Comput."},{"issue":"3\u20134","key":"15_CR15","doi-asserted-by":"crossref","first-page":"451","DOI":"10.3233\/FI-2014-1025","volume":"131","author":"K. Krithivasan","year":"2014","unstructured":"K. Krithivasan, Gh. P\u0103un, A. Ramanujan, On controlled P systems. Fundamenta Informaticae 131(3\u20134), 451\u2013464 (2014)","journal-title":"Fundamenta Informaticae"},{"key":"15_CR16","unstructured":"A. Leporati, A.E. Porreca, C. Zandron, G. Mauri, Improving universality results on parallel enzymatic numerical P systems, in Proc. 11th Brainstorming Week on Membrane Computing (F\u00e9nix Editora, Sevilla, 2013), pp. 177\u2013200"},{"key":"15_CR17","unstructured":"A. Leporati, A.E. Porreca, C. Zandron, G. Mauri, Enzymatic numerical P systems using elementary arithmetic operations, in Proc. 14th Intern. Conf. on Membrane Computing (Chi\u015fin\u0103u, Moldova, 2013), pp. 225\u2013240"},{"volume-title":"Pulsed Neural Networks","year":"1999","key":"15_CR18","unstructured":"W. Maass, C. Bishop (eds.) Pulsed Neural Networks (MIT Press, Cambridge, 1999)"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"M. Mutyam, K. Krithivasan, P systems with membrane creation: Universality and efficiency, in Proc. MCU 2001 ed. by M. Margenstern, Y. Rogozhin. LNCS, vol. 2055 (Springer, Berlin, 2001), pp. 276\u2013287","DOI":"10.1007\/3-540-45132-3_19"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"A.B. Pavel, C.I. Vasile, I. Dumitrache, Robot localization implemented with enzymatic numerical P systems, in Proc. Conf. Living Machines 2012, LNCS, vol. 7375 (Springer, 2012), pp. 204\u2013215","DOI":"10.1007\/978-3-642-31525-1_18"},{"key":"15_CR21","unstructured":"A. P\u0103un, Gh. P\u0103un, The power of communication: P systems with symport\/antiport. New Generat. Comput. 20, 295\u2013305 (2002) The symport\/antiport P systems were introduced here, and their universality was proved for rules of various complexities\/sizes. These results were improved in a large number of papers, until reaching universality for minimal symport and antiport rules."},{"key":"15_CR22","unstructured":"Gh. P\u0103un, Computing with membranes. J. Comput. Syst. Sci. 61(1), 108\u2013143 (2000) (and Turku Center for Computer Science-TUCS Report 208, November 1998, www.tucs.fi) This is the paper where membrane computing was initiated. The cell-like P systems are introduced, both with symbol objects and string objects, and for both cases the universality was proved (using the characterization of Turing computable sets of numbers as the length sets of languages generated by context-free matrix grammars with appearance checking; later, more direct and simple proofs were obtained, starting from register machines). In the case of strings, both rewriting and splicing rules were investigated."},{"issue":"1","key":"15_CR23","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1142\/S0129054100000090","volume":"11","author":"Gh. P\u0103un","year":"2000","unstructured":"Gh. P\u0103un, Computing with membranes\u2014A variant. Int. J. Found. Comput. Sci. 11(1), 167\u2013182 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"15_CR24","unstructured":"Gh. P\u0103un, P systems with active membranes: attacking NP-complete problems. J. Autom. Lang. Combinat. 6, 75\u201390 (2001) Membrane division was introduced here, in the general framework of P systems with active membranes (the membranes are explicit parts of the object evolution rules), and a polynomial semi-uniform solution to SAT is provided. Later, uniform solutions were obtained (also for other NP-complete problems)."},{"key":"15_CR25","unstructured":"Gh. P\u0103un, Membrane Computing. An Introduction (Springer, Berlin, 2002) This is the first survey of membrane computing, systematizing the notions and the results at only a few years after the initiation of this research area. After an informal introduction (\u201cMembrane computing\u2014what it is and what it is not\u201d) and a chapter providing the biological and the computability prerequisites for the rest of the book, one presents the cell-like P systems with symbol objects and multiset rewriting rules, the systems with symport\/antiport rules, the P systems with string objects, and then the tissue-like P systems; their computing power is investigated; then one passes to the computing efficiency (\u201cTrading space for time\u201d), considering P systems with membrane division, membrane creation, string replication, and precomputed resources. Two more chapters present \u201cfurther technical results\u201d and \u201c(attempts to get) back to reality.\u201d The book ends with a list of open problems and of universality results."},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Gh. P\u0103un, Towards \u201cfypercomputations\u201d (in membrane computing), in Languages Alive. Essays Dedicated to Jurgen Dassow on the Occasion of His 65 Birthdayed. by H. Bordihn, M. Kutrib, B. Truthe. LNCS, vol. 7300 (Springer, Berlin, 2012), pp. 207\u2013221 The term \u201cfypercomputation\u201d (coming from \u201cfast computation\u201d and reminding of \u201chypercomputation\u201d = a computation going beyond the \u201cTuring barrier\u201d) was coined to name situations when a computing device can solve NP-complete problems in polynomial time, hence when a significant efficiency speedup is obtained.","DOI":"10.1007\/978-3-642-31644-9_14"},{"key":"15_CR27","unstructured":"Gh. P\u0103un, Some open problems about catalytic, numerical and spiking neural P systems, in Proc. 14th Intern. Conf. on Membrane Computing (Chi\u015fin\u0103u, Moldova, 2013), pp. 25\u201334"},{"key":"15_CR28","first-page":"213","volume":"73","author":"Gh. P\u0103un","year":"2006","unstructured":"Gh. P\u0103un, R. P\u0103un, Membrane computing and economics: Numerical P systems. Fundamenta Informaticae 73, 213\u2013227 (2006)","journal-title":"Fundamenta Informaticae"},{"issue":"2","key":"15_CR29","doi-asserted-by":"crossref","first-page":"238","DOI":"10.15837\/ijccc.2010.2.2478","volume":"5","author":"Gh. P\u0103un","year":"2010","unstructured":"Gh. P\u0103un, M.J. P\u00e9rez-Jim\u00e9nez, Solving problems in a distributed way in membrane computing: dP systems. Int. J. Comput. Commun. Cont. 5(2), 238\u2013252 (2010)","journal-title":"Int. J. Comput. Commun. Cont."},{"key":"15_CR30","unstructured":"Gh. P\u0103un, G. Rozenberg, A. Salomaa (eds.) Handbook of Membrane Computing (Oxford University Press, 2010) The basics of membrane computing are given in the book [25] (translated in Chinese in 2013), but the domain has fast evolved beyond the contents of the volume; new classes of P systems were introduced; new results and applications were reported. This made both necessary and possible the editing of the present handbook, a comprehensive survey of membrane computing at the level of 2009. Its contents are a suggestive hint to the landscape of membrane computing: 1. An introduction to and an overview of membrane computing (Gh. P\u0103un, G. Rozenberg); 2. Cell biology for membrane computing (D. Besozzi, I.I. Ardelean); 3. Computability elements for membrane computing (Gh. P\u0103un, G. Rozenberg, A. Salomaa); 4. Catalytic P systems (R. Freund, O.H. Ibarra, A. P\u0103un, P. Sos\u00edk, H.-C. Yen); 5. Communication P systems (R. Freund, A. Alhazov, Y. Rogozhin, S. Verlan); 6. P automata (E. Csuhaj-Varj\u00fa, M. Oswald, G. Vaszil); 7. P systems with string objects (C. Ferretti, G. Mauri, C. Zandron); 8. Splicing P systems (S. Verlan, P. Frisco); 9. Tissue and population P systems (F. Bernardini, M. Gheorghe); 10. Conformon P systems (P. Frisco); 11. Active membranes (Gh. P\u0103un); 12. Complexity\u00a0\u2013 Membrane division, membrane creation (M.J. P\u00e9rez-Jim\u00e9nez, A. Riscos-N\u00fa\u00f1ez, \u00c1. Romero-Jim\u00e9nez, D. Woods); 13. Spiking neural P systems (O.H. Ibarra, A. Leporati, A. P\u0103un, S. Woodworth); 14. P systems with objects on membranes (M. Cavaliere, S.N. Krishna, A. P\u0103un, Gh. P\u0103un); 15. Petri nets and membrane computing (J. Kleijn, M. Koutny); 16. Semantics of P systems (G. Ciobanu); 17. Software for P systems (D. D\u00edaz-Pernil, C. Graciani, M.A. Guti\u00e9rrez-Naranjo, I. P\u00e9rez-Hurtado, M.J. P\u00e9rez-Jim\u00e9nez); 18. Probabilistic\/stochastic models (P. Cazzaniga, M. Gheorghe, N. Krasnogor, G. Mauri, D. Pescini, F.J. Romero-Campero); 19. Fundamentals of metabolic P systems (V. Manca); 20. Metabolic P dynamics (V. Manca); 21. Membrane algorithms (T.Y. Nishida, T. Shiotani, Y. Takahashi); 22. Membrane computing and computer science (R. Ceterchi, D. Sburlan); 23. Other developments; 23.1. P Colonies (A. Kelemenov\u00e1); 23.2. Time in membrane computing (M. Cavaliere, D. Sburlan); 23.3. Membrane computing and self-assembly (M. Gheorghe, N. Krasnogor); 23.4. Membrane computing and X-machines (P. Kefalas, I. Stamatopoulou, M. Gheorghe, G. Eleftherakis); 23.5. Q-UREM P systems (A. Leporati); 23.6. Membrane computing and economics (Gh. P\u0103un, R.A. P\u0103un); 23.7 Mobile membranes and mobile ambients (B. Aman, G. Ciobanu); 23.8. Other topics (Gh. P\u0103un, G. Rozenberg)"},{"issue":"4","key":"15_CR31","doi-asserted-by":"crossref","first-page":"397","DOI":"10.3233\/FI-1999-38404","volume":"38","author":"Gh. P\u0103un","year":"1999","unstructured":"Gh. P\u0103un, S. Yu, On synchronization in P systems. Fundamenta Informaticae 38(4), 397\u2013410 (1999)","journal-title":"Fundamenta Informaticae"},{"key":"15_CR32","unstructured":"M.J. P\u00e9rez-Jim\u00e9nez, A. Riscos-N\u00fa\u00f1ez, A. Romero-Jim\u00e9nez, Complexity\u2014 Membrane division and membrane creation. Chapter\u00a012 of [30]"},{"key":"15_CR33","unstructured":"P. Sos\u00edk, A catalytic P system with two catalysts generating a non-semilinear set. Romanian J. Inf. Sci. Technology 16(1), 3\u20139 (2013)"},{"key":"15_CR34","unstructured":"C.I. Vasile, A.B. Pavel, J. Kelemen, Implementing obstacle avoidance and follower behaviors on Koala robots using numerical P systems, in Tenth Brainstorming Week on Membrane Computing, vol.\u00a0II (Sevilla, 2012), pp. 215\u2013227"},{"key":"15_CR35","doi-asserted-by":"crossref","unstructured":"C. Zandron, C. Ferretti, G. Mauri, Solving NP-complete problems using P systems with active membranes, in Proc. Unconventional Models of Computation ed. by I. Antoniou et al. (Springer, 2000), pp. 289\u2013301 Among other results, one proves here the so-called \u201cMilano theorem,\u201d saying that P systems without membrane division cannot solve NP-complete problems in polynomial time (unless if P = NP)","DOI":"10.1007\/978-1-4471-0313-4_21"},{"key":"15_CR36","unstructured":"The P Systems Website, www.ppage.psystems.eu"}],"container-title":["Open Problems in Mathematics and Computational Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-10683-0_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T16:28:31Z","timestamp":1747844911000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-10683-0_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319106823","9783319106830"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-10683-0_15","relation":{},"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"11 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}