Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2008 Research Summary

Model-Based Membrane Computing

View Current Project Information

Chihhong Patrick Cheng and Edward A. Lee

Membrane computing is an area of computer science aiming to abstract computing ideas and models from the structure and the functioning of living cells [1]. The membrane system (called P-System hereafter) is a hypothetic model for parallel computation. It consists of membranes organized as a tree, where children of a certain tree node can be viewed as inner membranes of a certain membrane.

In each membrane there are characters floating within (like chemical compounds). We may thus regard those floating characters as a multiset. A transition from a multiset to a multiset (rewriting rule) corresponds to a chemical reaction in real world; there may be catalysts, priorities between the rewriting rules, output generation to the upper/lower level membrane, or the diminishing of a certain membrane. Transitions happen with maximum parallelism. There may be non-determinacy within.

Due to the built-in nature of maximal parallelism inherent in the model, P-Systems have a great potential for implementing massively parallel systems in an efficient way that would allow us to solve currently intractable problems once future biotechnology (or silicon-technology) gives way to a practical bio-realization (or chip-realization) [2].

In this project, we expect to achieve the following goals:
(a) Define the MoC of membrane computing that would be constructed in Ptolemy by restricting the general P-System;
(b) Develop a simulation tool that captures the concurrent motion for multiset changes; and
(c) (Optional) we seek to solve some open problems regarding to our restricted P-System model.

[1]
G. Paun and G. Rozenberg, "A Guide to Membrane Computing," Theoretical Computer Science, Vol. 287, No. 1, 2002, pp. 73-100.
[2]
O. H. Ibarra and H. C. Yen, "Deterministic Catalytic Systems are not Universal," Theoretical Computer Science, Vol. 363, No. 2, 2006, pp. 149-161.