<?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%">Agustín Riscos-Núñez</style></author><author><style face="normal" font="default" size="100%">Miquel Rius-Font</style></author><author><style face="normal" font="default" size="100%">Francisco J. Romero-Campero</style></author></authors></contributors><titles><title><style face="normal" font="default" size="100%">The Role of the Environment in Tissue P Systems with Cell Division</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><keywords><keyword><style  face="normal" font="default" size="100%">cell division</style></keyword><keyword><style  face="normal" font="default" size="100%">Computational Complexity</style></keyword><keyword><style  face="normal" font="default" size="100%">Environment of a tissue</style></keyword><keyword><style  face="normal" font="default" size="100%">Membrane computing</style></keyword><keyword><style  face="normal" font="default" size="100%">Tissue P Systems</style></keyword></keywords><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-complejidad.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%">89-104</style></pages><abstract><style face="normal" font="default" size="100%">Classical tissue P systems with cell division have a special alphabet whose
elements appear at the initial conﬁguration of the system in an arbitrary large number
of copies. These objects are shared in a distinguished place of the system, called the environment. Besides, the ability of these computing devices to have inﬁnite copies of some
objects has been widely exploited in the design of eﬃcient solutions to computationally
hard problems.
This paper deals with computational aspects of tissue P systems with cell division
where there is not an environment having the property mentioned above. Speciﬁcally,
we establish the relationships between the polynomial complexity class associated with
tissue P systems with cell division and with or without environment. As a consequence,
we prove that it is not necessary to have inﬁnite copies of some objects at the initial
conﬁguration in order to solve NP–complete problems in an eﬃcient way.</style></abstract></record></records></xml>