Informática
https://hdl.handle.net/11441/33181
2019-09-21T05:03:17ZNarrowing Frontiers of Efficiency with Evolutional Communication Rules and Cell Separation
https://hdl.handle.net/11441/84116
Narrowing Frontiers of Efficiency with Evolutional Communication Rules and Cell Separation
In the framework of Membrane Computing, several efficient solutions to computationally
hard problems have been given. To find new borderlines between families of
P systems that can solve them and the ones that cannot is an important way to tackle the
P versus NP problem. Adding syntactic and/or semantic ingredients can mean passing
from non-efficiency to presumably efficiency. Here, we try to get narrow frontiers, setting
the stage to adapt efficient solutions from a family of P systems to another one. In order
to do that, a solution to the SAT problem is given by means of a family of tissue P systems
with evolutional symport/antiport rules and cell separation with the restriction that both
the left-hand side and the right-hand side of the rules have at most two objects.
2018-01-01T00:00:00ZLimits on P Systems with Proteins and Without Division
https://hdl.handle.net/11441/84112
Limits on P Systems with Proteins and Without Division
In the field of Membrane Computing, computational complexity theory has
been widely studied trying to nd frontiers of efficiency by means of syntactic or semantical ingredients. The objective of this is to nd two kinds of systems, one non-efficient
and another one, at least, presumably efficient, that is, that can solve NP-complete prob-
lems in polynomial time, and adapt a solution of such a problem in the former. If it is
possible, then P = NP. Several borderlines have been defi ned, and new characterizations
of different types of membrane systems have been published.
In this work, a certain type of P system, where proteins act as a supporting element
for a rule to be red, is studied. In particular, while division rules, the abstraction of
cellular mitosis is forbidden, only problems from class P can be solved, in contrast to the
result obtained allowing them.
2018-01-01T00:00:00ZCharacterizing PSPACE with Shallow Non-Confluent P Systems
https://hdl.handle.net/11441/84092
Characterizing PSPACE with Shallow Non-Confluent P Systems
In P systems with active membranes, the question of understanding the
power of non-confluence within a polynomial time bound is still an open problem. It is
known that, for shallow P systems, that is, with only one level of nesting, non-con
uence
allows them to solve conjecturally harder problems than con
uent P systems, thus reaching PSPACE. Here we show that PSPACE is not only a bound, but actually an exact
characterization. Therefore, the power endowed by non-con
uence to shallow P systems
is equal to the power gained by con
uent P systems when non-elementary membrane
division and polynomial depth are allowed, thus suggesting a connection between the
roles of non-confluence and nesting depth.
2018-01-01T00:00:00ZSpiking Neural P Systems with Addition/Subtraction Computing on Synapses
https://hdl.handle.net/11441/83942
Spiking Neural P Systems with Addition/Subtraction Computing on Synapses
Spiking neural P systems (SN P systems, for short) are a class of distributed
and parallel computing models inspired from biological spiking neurons. In this paper,
we introduce a variant called SN P systems with addition/subtraction computing on
synapses (CSSN P systems). CSSN P systems are inspired and motivated by the shunting
inhibition of biological synapses, while incorporating ideas from dynamic graphs and
networks. We consider addition and subtraction operations on synapses, and prove that
CSSN P systems are computationally universal as number generators, under a normal
form (i.e. a simplifying set of restrictions).
2018-01-01T00:00:00Z