AbstractsComputer Science

Developing effcient simulators for cell machines

by Ramos Luis Macías




Institution: Universidad de Sevilla
Department:
Year: 2016
Keywords: membrane computing; cell machines
Posted: 02/05/2017
Record ID: 2118532
Full text PDF: http://hdl.handle.net/11441/36828


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… Advisors/Committee Members: Pérez Jiménez, Mario de Jesús (advisor), Valencia Cabrera, Luis (advisor), Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial (affiliation).