<?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%">Luis F. Macías-Ramos</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%">Agustín Riscos-Núñez</style></author><author><style face="normal" font="default" size="100%">Miquel Rius-Font</style></author></authors><secondary-authors><author><style face="normal" font="default" size="100%">Erzsebet Csuhaj-Varjú</style></author><author><style face="normal" font="default" size="100%">Marian Gheorghe</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%">György Vaszil</style></author></secondary-authors></contributors><titles><title><style face="normal" font="default" size="100%">The efficiency of tissue P systems with cell separation relies on the environment</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%">2013</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://link.springer.com/chapter/10.1007/978-3-642-36751-9_17</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><pages><style face="normal" font="default" size="100%">7762 (2013), 257-276</style></pages><abstract><style face="normal" font="default" size="100%">The classical definition of tissue P systems includes a distinguished alphabet with the special assumption that its elements are available in an arbitrarily large amount of copies. These objects are shared in a distinguished place of the system, called the environment. This ability of having infinitely many copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems by means of tissue P systems.
This paper deals with computational aspects of tissue P systems with cell separation where there is no such environment as described above. The main result is that only tractable problems can be efficiently solved by using this kind of P systems. Bearing in mind that NP–complete problems can be efficiently solved by using tissue P systems without environment and with cell division, we deduce that in the framework of tissue P systems without environment, the kind of rules (separation versus division) provides a new frontier of the tractability of decision problems.</style></abstract></record></records></xml>