dc.description.abstract | Membrane Computing, introduced by Gh. Paun at the end of 1998, is a relatively young branch of Natural Computing providing non-deterministic distributed parallel computing models whose computational devices are called
membrane systems or P systems. These systems are inspired by some basic
biological features, specifically by the structure and functioning of the living
cells, as well as from the way the cells are organized in tissues, organs, and
organisms.
There are basically three ways to categorize membrane systems: cell-like
P systems, tissue-like P systems, and neural-like P systems, also called Spiking Neural P systems (SN P systems, for short). Cell-like P systems arrange
a series of membranes in a hierarchical way, inspired by the inner structure
of the biological cells. Tissue-like P systems arrange elemental membranes
in nodes of a directed graph, inspired from the cell inter-communication in
tissues. Similarly, Spiking Neural P systems also arrange elemental membranes in nodes of a directed graph, while taking inspiration from the way
in which neurons exchange information by the transmission of electrical impulses (spikes) along axons.
In general, P systems operate by applying rewriting rules de_ned over
multisets of objects associated to the di_erent membranes, in a synchronized
non-deterministic maximally parallel way. P systems show a double level of
parallelism: a first level comprises parallel application of rules within individual membranes, while a second level comprises all the membranes working
simultaneously, that is, in parallel. These features make P systems powerful
computing devices. In particular, the double level of parallelism allows a
space-time tradeoff enabling the generation of an exponential workspace in
polynomial time. As such P systems are suitable to tackle relevant real-life
problems, usually involving NP-complete problems. Moreover, P systems are
excellent tools to investigate on the computational complexity boundaries, in
particular tackling the P versus NP problem. In this way, by studying how
the ingredients relative to their syntax and semantics a_ect to their ability to
e_ciently solve NP-complete problems, sharper frontiers between e_ciency
and non-efficiency can be discovered.
Despite of their attractive properties, working with P systems immediately drives to an important inconvenient: due to constraints of current technology, P systems are yet to be fully implemented in vivo, in vitro, or even in silico, because of their massively parallel, distributed, and non-deterministic
nature. Thus, practical computations of P systems are driven by silicon-
based simulators, and hence their potential results are compromised by the
physical limitations of silicon architectures. They are often inefficient or not suitable when dealing with some P system features, such as the exponential
workspace creation, non-determinism and massive parallelism.
Consequently, developing e_cient simulation tools for P systems becomes
an indispensable task in order to both assist in the computational complexity
study involving such systems, as well as in the development and verification
of solutions to relevant real-life problems.
The main contributions derived from the work object of this dissertation
are the following:
-Finding sharper computational complexity boundaries by modelling
solutions to NP-complete problems in terms of cell-like P systems in
CDC and CSC.
-Developing a simulation tools for membrane systems in CDC and CSC
within the P-Lingua framework. These tools have played a major role
as assistants in the speci_cation and formal verification of the aforementioned solutions.
-Defining new SN P systems variants and the corresponding simulation
tools, within the P-Lingua framework. Also, simulation support for a
wide range of existing SN P systems variants has been included into
that framework.
-Defining efficient simulation tools for Fuzzy Reasoning SN P systems
working on High Performance Computation platforms, namely CUDA-
enabled devices. | es |