<?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%">Mario J. Pérez-Jiménez</style></author><author><style face="normal" font="default" size="100%">Petr Sosik</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">Improving the Efficiency of Tissue P Systems with Cell Separation</style></title><secondary-title><style face="normal" font="default" size="100%">Tenth Brainstorming Week on Membrane Computing</style></secondary-title><tertiary-title><style face="normal" font="default" size="100%">Proceedings of the Tenth Brainstorming Week on Membrane Computing</style></tertiary-title></titles><dates><year><style  face="normal" font="default" size="100%">2012</style></year><pub-dates><date><style  face="normal" font="default" size="100%">02/2012</style></date></pub-dates></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.gcn.us.es/10BWMC/10BWMCvolII/papers/mario-sosik.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%">Seville, Spain</style></pub-location><volume><style face="normal" font="default" size="100%">II</style></volume><pages><style face="normal" font="default" size="100%">105-140</style></pages><abstract><style face="normal" font="default" size="100%">Cell ﬁssion process consists of the division of a cell into two new cells such
that the contents of the initial cell is distributed between the newly created cells. This
process is modelled by a new kind of cell separation rules in the framework of Membrane
Computing. Speciﬁcally, in tissue-like membrane systems, cell separation rules have been
considered joint with communication rules of the form symport/antiport. These models
are able to create an exponential workspace, expressed in terms of the number of cells,
in linear time. On the one hand, an eﬃcient and uniform solution to the SAT problem by
using cell separation and communication rules with length at most 8 has been recently
given. On the other hand, only tractable problems can be eﬃciently solved by using
cell separation and communication rules with length at most 1. Thus, in the framework
of tissue P systems with cell separation, and assuming that P is different from NP, a ﬁrst frontier
between eﬃciency and non-eﬃciency is obtained when passing from communication rules
with length 1 to communication rules with length at most 8.
In this paper we improve the previous result by showing that the SAT problem can be
solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Hence, we provide a new tractability borderline:
passing from 1 to 3 amounts to passing from non–eﬃciency to eﬃciency, assuming that
P is different from NP.</style></abstract></record></records></xml>