EAGER: Computing With Cells

University Of California-Santa Barbara, Santa Barbara CA

Investigators

Abstract

Natural Computing is computing inspired by nature. Examples are evolutionary algorithms, neural networks, molecular computing, and quantum computing. Membrane computing is a branch of natural computing that was recently initiated by G. Paun in his seminal paper, "Computing with Membranes". Membrane computing identifies an unconventional computing model, namely a P system, from natural phenomena of cell evolutions and chemical reactions. A membrane system is a computing model, which abstracts from the way living cells process chemical compounds in their compartmental structure. Regions defined by a membrane structure (or cells related by communication channels) contain multi-sets of objects that evolve according to given rules. The objects can be described by symbols or by strings of symbols. By using the rules in a nondeterministic (or probabilistic) maximally parallel manner, transitions between the system configurations can be obtained. A sequence of transitions is a computation of how the system is evolving. Various ways of controlling the transfer of objects from a region to another while applying the rules (as well as possibilities to dissolve, divide or create membranes) are considered in this area. Due to the built-in nature of maximal parallelism inherent in the model, P systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems, in much the same way as the promise of quantum and molecular computing. More recently, spiking neural P systems (SN P systems) were introduced with the aim of incorporating into membrane computing specific ideas from spiking neurons. In short, an SN P system consists of a set of neurons placed in the nodes of a directed graph and sending signals (spikes) along the arcs of the graph which are called synapses. The objects evolve by means of spiking rules placed in the nodes and enabled when the number of spikes present in the nodes fulfill specified patterns. When a spiking rule is executed in a neuron, spikes are produced and sent in parallel to all neurons connected by an outgoing synapse from the neuron where the rule was applied. SN P systems are a good model of neural computing. The focus in the proposed project is on fundamental topics such as computational complexity and characterizations of several variants of SN P systems, universality/non-universality of the different models, determinism versus non-determinism, various modes of parallelization, synchronization, synchronous versus asynchronous computations, relationships to well-known models of parallel computation, and verification problems.