Resumen de Developing effcient simulators for cell machines
Luis Felipe Macías Ramos
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 defined over multisets of objects associated to the diferent 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 efficiently solve NP-complete problems, sharper frontiers between efficiency 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 efficient 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.
