BWMC2015. Brainstorming Week on Membrane Computing (13th. 2015. Sevilla)
https://hdl.handle.net/11441/33343
2024-03-28T10:14:57ZSome Quick Research Topics
https://hdl.handle.net/11441/54145
Some Quick Research Topics
Some research topics are suggested, in a preliminary form, in most cases
dealing with (somewhat nonstandard) extensions of existing types of P systems.
2015-01-01T00:00:00ZThirteen Brainstorming Week on Membrane Computing Sevilla, February 2-6, 2015 : RGNC Report 1/2015
https://hdl.handle.net/11441/33139
Thirteen Brainstorming Week on Membrane Computing Sevilla, February 2-6, 2015 : RGNC Report 1/2015
Research Group on Natural Computing
2015-01-01T00:00:00ZComputational Efficiency of P Systems with Symport/Antiport Rules and Membrane Separation
https://hdl.handle.net/11441/33124
Computational Efficiency of P Systems with Symport/Antiport Rules and Membrane Separation
Membrane ssion is a process by which a biological membrane is split into
two new ones in such a way that the contents of the initial membrane is separated and distributed
between the new membranes. Inspired by this biological phenomenon, membrane
separation rules were considered in membrane computing. In this paper we deal with celllike
P systems with membrane separation rules that use symport/antiport rules (such
systems compute by changing the places of objects with respect to the membranes, and
not by changing the objects themselves) as communication rules. Speci cally we study
a lower bound on the length of communication rules with respect to the computational
e ciency of such kind of membrane systems; that is, their ability to solve computationally
hard problems in polynomial time by trading space for time. The main result of this
paper is the following: communication rules involving at most three objects is enough
to achieve the computational e ciency of P systems with membrane separation. Thus,
a polynomial time solution to SAT problem is provided in this computing framework. It
is known that only problems in P can be solved in polynomial time by using minimal
cooperation in communication rules and membrane separation, so the lower bound of the
e ciency obtained is an optimal bound.
2015-01-01T00:00:00ZMinimal Cooperation in P Systems with Symport/Antiport: A Complexity Approach
https://hdl.handle.net/11441/33122
Minimal Cooperation in P Systems with Symport/Antiport: A Complexity Approach
Membrane systems with symport/antiport rules compute by just moving
objects among membranes, and not by changing the objects themselves. In these systems
the environment plays an active role because, not only it receives objects from the system,
but it also sends objects into the system. Actually, in this framework it is commonly
assumed that an arbitrarily large number of copies of some objects are initially available
in the environment. This special feature has been widely exploited for the design of
e cient solutions to computationally hard problems in the framework of tissue like P
systems able to create an exponential workspace in polynomial time (e.g. via cell division
or cell separation rules).
This paper deals with cell-like P systems which use symport/antiport rules as communication
rules, and the role played by the minimal cooperation is studied from a computational
complexity point of view. Speci cally, the limitations on the e ciency of P systems
with membrane separation whose symport/antiport rules involve at most two objects are
established. In addition, a polynomial time solution to HAM-CYCLE problem, a well known
NP-complete problem, by using a family of such kind of P systems with membrane
division, is provided. Therefore, in the framework of cell-like P systems with minimal
cooperation in communication rules, passing from membrane separation to membrane
division amounts to passing from tractability to NP{hardness.
2015-01-01T00:00:00Z