<?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%">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></records></xml>