loading...
Computing with Cells: Membrane Systems
May 07-May 09
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/I-SPAN.2008.12The International Symposium on Parall ...
 This Article 
 
PURCHASE ARTICLE: $0
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Membrane computing, first introduced in 1998 by Gheorghe P\u aun, is a part of the general research effort of describing and investigating computing models, ideas, architectures, and paradigms from the processes taking place in nature. It is a branch of molecular computing that is motivated by cell biology. Membrane computing identifies an unconventional computing model, namely a P system, which abstracts from the way living cells process chemical compounds in their compartmental structure. Regions defined by a membrane structure contain multisets of objects that evolve according to specified rules. The objects can be represented as symbols or strings of symbols. By using the rules in a nondeterministic (deterministic) maximally parallel manner, transitions between the system configurationscan be obtained. A sequence of transitions is a computation of how the system is evolving. Various ways of controlling the transfer of objects from one region to another and applying the rules, as well as possibilities to dissolve, divide or create membranes have been studied. P systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems once future bio-technology gives way to a practical bio-realization. Since its introduction, the literature in this area has grown rapidly (in 2003, the Institute for Scientific Information designated the intial paper as "fast breaking'' and the domain as an "emerging research front in computer science''). We give a brief overview of membrane computing and report on recent results that answer some interesting and fundamental open questions in the field. We also look at the recently introduced neural-like systems, called spiking neural P systems. These systems incorporate the ideas of spiking neurons into membrane computing. We present various classes and characterize their computing power and complexity. In particular, we analyze asynchronous and sequential systems and present some conditions under which they become (non-)universal. The non-universal variants are characterized by monotonic counter machines and partially blind countermachines. The latter devices are known to be equivalent to vector addition systems (or Petri nets) and, hence, have many decidable properties.
Index Terms:
Membrane computing, P system, spiking neural P system
Citation:
Oscar H. Ibarra, "Computing with Cells: Membrane Systems," ispan, pp.3, The International Symposium on Parallel Architectures, Algorithms, and Networks (i-span 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.