<?xml version="1.0" encoding="UTF-8"?><xml><records><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Paolo Cazzaniga</style></author><author><style face="normal" font="default" size="100%">Marian Gheorghe</style></author><author><style face="normal" font="default" size="100%">Natalio Krasnogor</style></author><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Dario Pescini</style></author><author><style face="normal" font="default" size="100%">Francisco J. Romero-Campero</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Grzegorz Rozenberg</style></author><author><style face="normal" font="default" size="100%">Arto Salomaa</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">Probabilistic/Stochastic Models</style></title><secondary-title><style face="normal" font="default" size="100%">The Oxford Handbook of Membrane Computing</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2010</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.oup.com.au/titles/academic/maths/9780199556670</style></url></web-urls></urls><section><style face="normal" font="default" size="100%">18</style></section><publisher><style face="normal" font="default" size="100%">Oxford University Press</style></publisher><pub-location><style face="normal" font="default" size="100%">Oxford (U.K.)</style></pub-location><pages><style face="normal" font="default" size="100%">455-474</style></pages><isbn><style face="normal" font="default" size="100%">9780199556670</style></isbn></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Alberto Leporati</style></author><author><style face="normal" font="default" size="100%">Claudio Ferretti</style></author><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Complexity aspects of polarizationless membrane systems</style></title><secondary-title><style face="normal" font="default" size="100%">Natural Computing</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2009</style></year><pub-dates><date><style  face="normal" font="default" size="100%">12/2009</style></date></pub-dates></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.springerlink.com/content/a8q346311328p807/</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Springer Verlag</style></publisher><pub-location><style face="normal" font="default" size="100%">Amsterdam, Netherlands</style></pub-location><volume><style face="normal" font="default" size="100%">8</style></volume><pages><style face="normal" font="default" size="100%">703-717</style></pages><abstract><style face="normal" font="default" size="100%">We investigate polarizationless P systems with active membranes working in maximally parallel manner, which do not make use of evolution or communication rules, in order to find which features are sufficient to efficiently solve computationally hard problems. We show that such systems are able to solve the PSPACE-complete problem Quantified 3-sat, provided that non-elementary membrane division is controlled by the presence of a (possibly non-elementary) membrane.</style></abstract><issue><style face="normal" font="default" size="100%">4</style></issue></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Alberto Leporati</style></author><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Uniform solutions to SAT and Subset Sum by spiking neural P systems</style></title><secondary-title><style face="normal" font="default" size="100%">Natural Computing</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">Membrane computing; Spiking neural P system; SAT problem; Subset sum problem; Complexity</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2009</style></year><pub-dates><date><style  face="normal" font="default" size="100%">12/2009</style></date></pub-dates></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://dx.doi.org/10.1007/s11047-008-9091-y</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Springer Verlag</style></publisher><pub-location><style face="normal" font="default" size="100%">Amsterdam, Netherlands</style></pub-location><volume><style face="normal" font="default" size="100%">8</style></volume><pages><style face="normal" font="default" size="100%">681-702</style></pages><abstract><style face="normal" font="default" size="100%">We continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally hard problems, addressing two problems which were already recently considered in this respect: SubsetSum and SAT. For both of them we provide uniform constructions of standard spiking neural P systems (i.e., not using extended rules or parallel use of rules) which solve these problems in a constant number of steps, working in a non-deterministic way. This improves known results of this type where the construction was non-uniform, and/or was using various ingredients added to the initial definition of spiking neural P systems (the SN P systems as defined initially are called here “standard”). However, in the SubsetSum case, a price to pay for this improvement is that the solution is obtained either in a time which depends on the value of the numbers involved in the problem, or by using a system whose size depends on the same values, or again by using complicated regular expressions. A uniform solution to SAT is also provided, that works in constant time. </style></abstract><issue><style face="normal" font="default" size="100%">4</style></issue></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author><author><style face="normal" font="default" size="100%">Alberto Leporati</style></author><author><style face="normal" font="default" size="100%">Claudio Ferretti</style></author><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution</style></title><secondary-title><style face="normal" font="default" size="100%">Fundamenta Informaticae</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2008</style></year><pub-dates><date><style  face="normal" font="default" size="100%">09/2008</style></date></pub-dates></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://portal.acm.org/citation.cfm?id=1487719&dl=GUIDE,</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">IOS Press</style></publisher><pub-location><style face="normal" font="default" size="100%">Warsaw, Poland</style></pub-location><volume><style face="normal" font="default" size="100%">87</style></volume><pages><style face="normal" font="default" size="100%">79-91</style></pages><abstract><style face="normal" font="default" size="100%">Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-SAT by using only dissolution rules and a form of strong division for non-elementary membranes, working in the maximallly parallel way.</style></abstract><issue><style face="normal" font="default" size="100%">1</style></issue><custom1><style face="normal" font="default" size="100%">0.715</style></custom1><custom2><style face="normal" font="default" size="100%">102/175 - Q3</style></custom2></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author><author><style face="normal" font="default" size="100%">Alberto Leporati</style></author><author><style face="normal" font="default" size="100%">Claudio Ferretti</style></author><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution</style></title><secondary-title><style face="normal" font="default" size="100%">6th Brainstorming Week on Membrane Computing</style></secondary-title><tertiary-title><style face="normal" font="default" size="100%">Proceedings of the Sixth Brainstorming Week on Membrane Computing</style></tertiary-title></titles><dates><year><style  face="normal" font="default" size="100%">2008</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.gcn.us.es/6BWMC/volume/strongdivision.pdf</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Fénix Editora</style></publisher><pub-location><style face="normal" font="default" size="100%">Sevilla, Spain</style></pub-location><volume><style face="normal" font="default" size="100%">6</style></volume><pages><style face="normal" font="default" size="100%">261-274</style></pages><isbn><style face="normal" font="default" size="100%">978-84-612-44 </style></isbn><abstract><style face="normal" font="default" size="100%">Recognizer P systems with active membranes have proven to be very powerful
computing devices, being able to solve NP-complete decision problems in a polynomial
time. However such solutions usually exploit many powerful features, such as electrical
charges (polarizations) associated to membranes, evolution rules, communication rules,
and strong or weak forms of division rules. In this paper we contribute to the study
of the computational power of polarizationless recognizer P systems with active membranes.
Precisely, we show that such systems are able to solve in polynomial time the
NP-complete decision problem 3-sat by using only dissolution rules and a form of strong
division for non–elementary membranes, working in the maximal parallel way.</style></abstract></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">On a Paun's conjecture in membrane systems</style></title><secondary-title><style face="normal" font="default" size="100%">Lecture Notes in Computer Science</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2007</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://dx.doi.org/10.1007/978-3-540-73053-8_18</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Springer</style></publisher><pub-location><style face="normal" font="default" size="100%">Amsterdam, The Netherlands</style></pub-location><volume><style face="normal" font="default" size="100%">4527</style></volume><pages><style face="normal" font="default" size="100%">180-192</style></pages><isbn><style face="normal" font="default" size="100%">978-3-540-73052-1</style></isbn><abstract><style face="normal" font="default" size="100%">We study a Păun’s conjecture concerning the unsolvability of NP–complete problems by polarizationless P systems with active membranes in the usual framework, without cooperation, without priorities, without changing labels, using evolution, communication, dissolution and division rules, and working in maximal parallel manner. We also analyse a version of this conjecture where we consider polarizationless P systems working in the minimally parallel manner. 
</style></abstract></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author><author><style face="normal" font="default" size="100%">Grzegorz Rozenberg</style></author><author><style face="normal" font="default" size="100%">Arto Salomaa</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Membrane Computing (5th International Workshop, WMC 2004, Revised, Selected and Invited Papers).</style></title><secondary-title><style face="normal" font="default" size="100%">Lecture Notes in Computer Science</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">bioinformatics</style></keyword><keyword><style  face="normal" font="default" size="100%">Biologically inspired computing</style></keyword><keyword><style  face="normal" font="default" size="100%">cell communication</style></keyword><keyword><style  face="normal" font="default" size="100%">complexity theory</style></keyword><keyword><style  face="normal" font="default" size="100%">formal languages</style></keyword><keyword><style  face="normal" font="default" size="100%">information processing in cells</style></keyword><keyword><style  face="normal" font="default" size="100%">Membrane computing</style></keyword><keyword><style  face="normal" font="default" size="100%">membrane systems</style></keyword><keyword><style  face="normal" font="default" size="100%">molecular computing</style></keyword><keyword><style  face="normal" font="default" size="100%">Natural computing</style></keyword><keyword><style  face="normal" font="default" size="100%">P systems</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2005</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.springeronline.com/sgw/cda/frontpage/0,11855,5-156-22-44223445-0,00.html</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Springer-Verlag</style></publisher><pub-location><style face="normal" font="default" size="100%">Berlín, Alemania</style></pub-location><volume><style face="normal" font="default" size="100%">3365</style></volume><pages><style face="normal" font="default" size="100%">IX+415</style></pages><isbn><style face="normal" font="default" size="100%">3-540-25080-8</style></isbn><notes><style face="normal" font="default" size="100%">Giancarlo Mauri; Gheorghe Paun; Mario J. Pérez-Jiménez; Grzegorz Rozenberg; Arto Salomaa (eds.) </style></notes></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Rodica Ceterchi</style></author><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">Simulating parallel architectures with P systems</style></title><secondary-title><style face="normal" font="default" size="100%">Workshop on Membrane Computing, WMC5</style></secondary-title><tertiary-title><style face="normal" font="default" size="100%">Pre-proceedings of the Fifth Workshop on Membrane Computing</style></tertiary-title></titles><dates><year><style  face="normal" font="default" size="100%">2004</style></year><pub-dates><date><style  face="normal" font="default" size="100%">June 14-16, 2004</style></date></pub-dates></dates><pub-location><style face="normal" font="default" size="100%">Milán, Italia</style></pub-location><pages><style face="normal" font="default" size="100%">184-185</style></pages></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Mario J. Pérez-Jiménez</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">Computational Complexity in P Systems</style></title><secondary-title><style face="normal" font="default" size="100%">Workshop on Membrane Computing, WMC5</style></secondary-title><tertiary-title><style face="normal" font="default" size="100%">Pre-proceedings of the Fifth Workshop on Membrane Computing</style></tertiary-title></titles><dates><year><style  face="normal" font="default" size="100%">2004</style></year><pub-dates><date><style  face="normal" font="default" size="100%">June 14-16</style></date></pub-dates></dates><urls><related-urls><url><style face="normal" font="default" size="100%">http://www.gcn.us.es/files/Computational Complexity in P Systems.pdf</style></url></related-urls></urls><pub-location><style face="normal" font="default" size="100%">Milán, Italia</style></pub-location><pages><style face="normal" font="default" size="100%">63</style></pages></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Grzegorz Rozenberg</style></author><author><style face="normal" font="default" size="100%">Arto Salomaa</style></author><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Carlos Martín-Vide</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Membrane Computing (International Workshop, WMC 2003, Revised Papers)</style></title></titles><dates><year><style  face="normal" font="default" size="100%">2004</style></year></dates><publisher><style face="normal" font="default" size="100%">Springer-Verlag</style></publisher><pub-location><style face="normal" font="default" size="100%">Berlín Alemania</style></pub-location><pages><style face="normal" font="default" size="100%">383</style></pages><isbn><style face="normal" font="default" size="100%">3-540-20895-X</style></isbn><notes><style face="normal" font="default" size="100%">Gheorghe Paun; Grzegorz Rozenberg; Arto Salomaa; Giancarlo Mauri; Carlos Martín-Vide (eds.)</style></notes></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>10</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Pre-proceedings of the Fifth Workshop on Membrane Computing, WMC5</style></title><secondary-title><style face="normal" font="default" size="100%">Workshop on Membrane Computing, WMC5</style></secondary-title></titles><dates><year><style  face="normal" font="default" size="100%">2004</style></year></dates><pub-location><style face="normal" font="default" size="100%">Milán, Italia</style></pub-location></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Daniela Besozzi</style></author><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Gemmating P systems: collapsing hierarchies </style></title><secondary-title><style face="normal" font="default" size="100%">Theoretical Computer Science</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">matrix grammar</style></keyword><keyword><style  face="normal" font="default" size="100%">Membrane computing</style></keyword><keyword><style  face="normal" font="default" size="100%">recursively enumerable languages</style></keyword><keyword><style  face="normal" font="default" size="100%">Universality</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2003</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://linkinghub.elsevier.com/retrieve/pii/S0304397502006576</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Elsevier</style></publisher><pub-location><style face="normal" font="default" size="100%">Amsterdam (The Netherlands)</style></pub-location><volume><style face="normal" font="default" size="100%">296</style></volume><pages><style face="normal" font="default" size="100%">253-267 </style></pages><abstract><style face="normal" font="default" size="100%">We continue the analysis of P systems with gemmation of mobile membranes. We solve an open problem from Besozzi et al. (Proc. Italian Conf. on Theoretical Computer Science 2001, Lecture Notes in Computer Science, Vol. 2202, Springer, Berlin, 2001, pp. 136–153), showing that the hierarchy on the number of membranes collapses: systems with eight membranes characterize the recursively enumerable languages (seven membranes are enough in the case of extended systems). We also prove that P systems, which use only gemmation, but neither classical rewriting rules nor in/out communications, can generate the same family of languages. In this case, the hierarchy on the number of membranes collapses to level nine. 

</style></abstract><issue><style face="normal" font="default" size="100%">2</style></issue></record><record><source-app name="Biblio" version="6.x">Drupal-Biblio</source-app><ref-type>13</ref-type><contributors><authors><author><style face="normal" font="default" size="100%">Claudio Ferretti</style></author><author><style face="normal" font="default" size="100%">Giancarlo Mauri</style></author><author><style face="normal" font="default" size="100%">Gheorghe Paun</style></author><author><style face="normal" font="default" size="100%">Claudio Zandron</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">On three variants of rewriting P systems </style></title><secondary-title><style face="normal" font="default" size="100%">Theoretical Computer Science</style></secondary-title></titles><keywords><keyword><style  face="normal" font="default" size="100%">chomsky hierarchy</style></keyword><keyword><style  face="normal" font="default" size="100%">Lindenmayer systems</style></keyword><keyword><style  face="normal" font="default" size="100%">Membrane computing</style></keyword><keyword><style  face="normal" font="default" size="100%">regulated rewriting</style></keyword></keywords><dates><year><style  face="normal" font="default" size="100%">2003</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.ingentaconnect.com/content/els/03043975/2003/00000301/00000001/art00581</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Elsevier</style></publisher><pub-location><style face="normal" font="default" size="100%">Amsterdam (The Netherlands)</style></pub-location><volume><style face="normal" font="default" size="100%">301</style></volume><pages><style face="normal" font="default" size="100%">201-215</style></pages><abstract><style face="normal" font="default" size="100%">We continue here the study of P systems with string objects processed by rewriting rules, by investigating some questions which are classic in formal language theory: leftmost derivation, conditional use of rules (permitting and forbidding conditions), relationships with language families in Chomsky and Lindenmayer hierarchies.

</style></abstract><issue><style face="normal" font="default" size="100%">1</style></issue></record></records></xml>