Introduction
P systems were introduced by Gh. Pãun (see DassowPaun98, Paun98) as distributed parallel computing devices, based on inspiration from biochemistry, especially with respect to the structure and the functioning of a living cell. The cell is considered as a set of compartments enclosed by membranes; the membranes are nested one in another and contain objects and evolution rules. The basic model neither specifies the nature of these objects nor the nature of the rules. Specifying these two parameters, a lot of different models of computing have been introduced, see Ppage for a comprehensive bibliography. Tissue P systems, first considered by Gh. Pãun and T. Yokomori in PaunEtal02 and PaunYokomori99, also see FreundEtal05, use the graph topology in contrast to the tree topology used in the basic model of P systems.
In this paper, we design a general class of multiset rewriting systems containing, in particular, P systems and tissue P systems. We recall that any P system may be seen at the most abstract level as a multiset rewriting system with only one compartment, encoding the membrane as part of the object representation. However, this approach completely ignores the inner structure of the system because all structural information is hidden (by an encoding) which makes it difficult do deduce any compartment-related information or to model (processes in) biological systems. At a lower level of abstraction, a P system may be seen as networks of cells (compartments) evolving with multi-cell multiset rewriting rules. At the lowest level, the graph/tree structure appears as well as a specialization of rules which are of a very particular form. This last level is usually used in the area of P systems because it permits to easily specify the system and to incorporate different new types of rules.
It is worth noting that in the definition of membrane systems the application of rules often is defined in a quite informal way. This is related to the fact that for a long time only the maximally parallel derivation mode was considered and a P system was supposed to work only in this mode. Recent developments in P systems area have revealed that other derivation modes as the minimally parallel derivation mode might be considered CiobanuEtal06 and allow for many interesting new results, yet depending on specific interpretations of this notion. Moreover, different halting conditions have been investigated (see FreundOswald07, Alhazov07), too. All these articles have shown that there is a need for a formal definition of part of the semantics of membrane systems as the derivation step and the halting procedure like it was done for splicing test tube systems CsuhajEtal96 or networks of language processors Csuhaj01. In particular, this is important for a classification of P systems as well as for their implementation. For approaches to find operational and logic based semantics for P systems we refer to CiobanuEtal05 and CiobanuEtal07; a Petri net semantics for membrane systems is discussed in KleijnEtal2005.
This article is an attempt to fulfill the goal of formally defining a procedural semantics for a quite large number of well-known variants of P systems considered so far in the literature, but, of course, we do not at all claim to have captured all the variants having already appeared in the literature. In order to be quite general we place our reasoning at the abstract level of networks of cells, already considered in a slightly different way in BernardiniEtal07. We adapt an implementational point of view and also give a formal definition of the derivation step, the halting condition and the procedure for obtaining the result of a computation. Moreover, we give examples of applying our concepts to some well-known variants of P systems.
Read the complete paper (Rudolf FREUND, Sergey VERLAN: A Formal Framework for P Systems): psemanticsf.pdf
References
Alhazov07: A. Alhazov, R. Freund, M. Oswald, S. Verlan: Partial versus total halting in P systems. Proc. Fifth Brainstorming Week on Membrane Computing, Sevilla, 2007, to appear.
CiobanuEtal07: O. Andrei, G. Ciobanu, D. Lucanu: A rewriting logic framework for operational semantics of membrane systems, Theoretical Computer Science 373, 3 (2007), 163-181.
BernardiniEtal07: F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan: Networks of Cells and Petri Nets. Proc. Fifth Brainstorming Week on Membrane Computing, Sevilla, 2007, to appear.
CiobanuEtal05: G. Ciobanu, O. Andrei, D. Lucanu: Structural operational semantics of P systems. In: WMC6, 1-23.
Ciobanuetal06: G. Ciobanu, L. Pan, Gh. Pãun, M.J. Pérez-Jiménez: P systems with minimal parallelism, accepted for TCS.
CsuhajEtal96: E. Csuhaj-Varjú, L. Kari, and Gh. Pãun: Test tube distributed systems based on splicing. Computers and AI 15 (2-3) (1996), 211-232.
Csuhaj01: E. Csuhaj-Varjú: Networks of Language Processors. Current Trends in Theoretical Computer Science (2001), 771-790.
DassowPaun98: J. Dassow, Gh. Pãun: On the power of membrane computing, Journal of Universal Computer Science 5 (2) (1999), 33-49.
WMC6: R. Freund, G. Lojka, M. Oswald, Gh. Pãun (Eds.): Pre-Proceedings of Sixth International Workshop on Membrane Computing (WMC6), Vienna, June 18-21, 2005.
FreundOswald07: R. Freund, M. Oswald: P systems with partial halting, accepted, 2007.
FreundEtal05: R. Freund, Gh. Pãun, M.J. Pérez-Jiménez: Tissue-like P systems with channel states. Theoretical Computer Science 330 (2005), 101-116.
KleijnEtal2005: J. Kleijn, M. Koutny, G. Rozenberg: Towards a Petri net semantics for membrane systems. In: WMC6, 439-460.
Pauns02: A. Pãun, Gh. Pãun: The power of communication: P systems with symport/ antiport, New Generation Computing 20, 3 (2002), 295-306.
Paun98: Gh. Pãun: Computing with membranes, J. of Computer and System Sciences 61, 1 (2000), 108-143, and TUCS Research Report 208 (1998) (http://www.tucs.fi).
Paunbook02: Gh. Pãun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002.
RogozhinEtal06: Y. Rogozhin, A. Alhazov, R. Freund: Computational power of symport/antiport: history, advances, and open problems. In: R. Freund, Gh. Pãun, G. Rozenberg, A. Salomaa (Eds.): Membrane Computing. 6th International Workshop WMC 2005, Vienna, Austria, Lecture Notes in Computer Science 3850, Springer-Verlag, 2006, 1-30.
handbook97: G. Rozenberg, A.Salomaa (Eds.): Handbook of Formal Languages (3 volumes), Springer-Verlag, Berlin, 1997.
PaunEtal02: Gh. Pãun, Y. Sakakibara, and T. Yokomori: P systems on graphs of restricted forms. Publicationes Matimaticae 60, 2002.
PaunYokomori99: Gh. Pãun and T. Yokomori: Membrane computing based on splicing. In: E. Winfree and D.K. Gifford (Eds.), DNA Based Computers V, volume 54 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 217-232. American Mathematical Society, 1999.
Ppage: The P Systems Web Page: http://psystems.disco.unimib.it.