<?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%">A polynomial alternative to unbounded environment for tissue P systems with cell division</style></title><secondary-title><style face="normal" font="default" size="100%">International Journal of Computer Mathematics</style></secondary-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%">2013</style></year></dates><urls><web-urls><url><style face="normal" font="default" size="100%">http://www.tandfonline.com/doi/abs/10.1080/00207160.2012.748898</style></url></web-urls></urls><publisher><style face="normal" font="default" size="100%">Taylor and Francis</style></publisher><pub-location><style face="normal" font="default" size="100%">London, UK</style></pub-location><volume><style face="normal" font="default" size="100%">90</style></volume><pages><style face="normal" font="default" size="100%">760-775</style></pages><abstract><style face="normal" font="default" size="100%">The standard definition of tissue P systems includes a special alphabet whose elements are assumed to appear in the initial configuration of the system in an arbitrarily large number of copies. These objects reside in a distinguished place of the system, called the environment. Such potentially infinite supply of objects seems an unfair tool when designing efficient solutions to computationally hard problems in the framework of membrane computing, by performing a space–time trade-off.

This paper deals with computational aspects of tissue P systems with cell division where there is no environment having the property mentioned above. Specifically, we prove that the polynomial complexity classes associated with tissue P systems with cell division and with or without environment are actually identical. As a consequence, we conclude that it is not necessary to have infinitely many copies of some objects in the initial configuration in order to solve NP–complete problems in an efficient way.</style></abstract><issue><style face="normal" font="default" size="100%">4</style></issue><custom1><style face="normal" font="default" size="100%">0.542</style></custom1><custom2><style face="normal" font="default" size="100%">173/247 - Q3</style></custom2></record></records></xml>