Membrane Computing 

Gheorghe Păun:
Membrane Computing,
an introduction.
Natural Computing Series, Springer, 2002. ISBN: 3540436014 Pierluigi Frisco: Computing with Cells: Advances in Membrane Computing. OUP, 2009 ISBN: 0199542864 
presentation (pdf)
(Based on DLT'02 and WMC'02) H.J. Hoogeboom
presentation (pdf)
P systems web page (Milano)
Three Leiden PhD students presented a thesis (partially) in membrane computing. Pierluigi Frisco. Theory of Molecular Programming — Splicing and Membrane systems. Ph.D. Thesis, Universiteit Leiden, May 2004. Robert Brijder. Models of Natural Computation: Gene Assembly and Membrane Systems. Ph.D. Thesis, Universiteit Leiden, december 2008. repository Jun Wang 汪隽. Spiking Neural P Systems. Ph.D. Thesis, Universiteit Leiden, december 2011. repository / papers Thís page is devoted to inert (nonreactive) P systems, where computation is performed by communication, and by moving objects around the system. Simple and elegant. 
P systems with Carriers 

Introduced in: C. MartínVide, Gh. Păun, G. Rozenberg, Membrane Systems with Carriers, Theoretical Computer Science 270 (2002) 779796. »
rules (associated to region) for multiset x carrier v:

H.J. Hoogeboom.
Carriers and Counters: P systems with Carriers vs. (Partially Blind) Counter Automata. In: M. Ito and M. Toyama (Eds.) Developments in Language Theory, 6th International Conference, DLT 2002, Kyoto, Japan, September 1821, 2002, Revised Papers. pages 140151. Lecture Notes in Computer Science 2450, Springer Verlag 2003. abstract: P systems with carriers are shown to be computationally complete with only one membrane and two carriers. We argue that their power is due to the maximal parallelism required in the application of the rules. In fact, with a single carrier, these systems are equivalent to partially blind counter automata. Finally, with a single passenger restriction the systems are again computationally complete. nb. partially was added to be slightly more in line with usual terminology! N·CP_{m}(c,p), where the parameters represent the number of membranes, carriers, and passengers per carrier, respectively.
Theorem 1.
N·RE = N·CP_{1}(2,3)

(12.1'05)  There is some recent interest in clockless P systems, i.e., systems without maximal parallellism. We quote a relevant part of the introduction: "The real value of our construction is that it suggests that the key feature of P systems responsible for universality is the requirement of maximal parallelism, that is, a computational step is illegal if it can be extended by applying another rule to objects not yet involved in the step. To support this conjecture, we show in Section 4 that carrier P systems that do not require maximal parallelism in their computational steps can be simulated by a blind counter automaton, i.e., a counter automaton unable to perform zero tests. This makes the situation similar to Petri nets, where adding maximal parallelism also gives universality [Bu81]. In the single carrier case there is no room for parallelism and we characterize the languages of single carrier systems as the partially blind counter languages, Corollary 4." 


Y. Gao, H.J. Hoogeboom.
P Systems with Single Passenger Carriers.
International Journal of Foundations of Computer Science 17 (2007) 12271235.
abstract: Membrane systems with carriers holding only a single passenger are known to be computationally complete, although this result does not bound the number of membranes and the number of carriers. We show that actually two membranes suffice. Theorem 2. N·RE = N·CP_{2}(*,1) 

P systems with Symport/Antiport 

Introduced in: A. Păun, Gh. Păun. The Power of Communication: P Systems with Symport/Antiport. New Generation Computing, 20 (2002), pages 295305.
rules (associated to membrane) for multisets x,y:

P. Frisco, H.J. Hoogeboom.
Simulating counter automata by P systems with symport/antiport. In: Membrane Computing: International Workshop, WMCCdeA 2002, Curtea de Argeş, Romania, August 1923, 2002. Revised Papers. Lecture Notes in Computer Science 2597, Springer Verlag 2003. abstract: The complexity, expressed in number of membranes and weight of rules, of P systems with symport/antiport generating recursively enumerable sets is reduced if counter automata instead of matrix grammars are simulated. We consider both subsets of N obtained by counting objects in a designated membrane, and string languages obtained by following the traces of a designated object.
P systems with Symport/Antiport
Following the Traces
Numbering of results as in the full paper: 
postscriptum 28.10'04 
F. Bernardini and M. Gheorghe use new ideas for minimal symport/antiport to show that N·RE = N·PP_{9}(sym_{1},anti_{1}), see their paper at the Workshop on Membrane Computing; Tarragona, July 1722 2003. 
postscriptum 4.1'06 
A. Alhazov, M. Margenstern, V. Rogozhin, Yu. Rogozhin, S. Verlan bring the number of membranes down to three, after intermediate results by others: «Communicative P Systems with Minimal Cooperation», WMC 2004, Milano June 1416, 2004, LNCS 3365, 2005. 
Overview and further ramifications are given in: A. Alhazov, R. Freund, Y. Rogozhin; «Computational Power of Symport/Antiport: History, Advances, and Open Problems», WMC 2005, Vienna, Austria, July 1821, 2005, LNCS 3850, 2006 (pages 1  30) doi 10.1007/11603047_1  
up up^{2} 