Formal Definitions Network Of Cells

Network of Cells

We consider a general framework for describing membrane systems with a static membrane structure, i.e., membrane systems as a collection of interacting cells containing multisets of objects.

A network of cells of degree n\geq 1 (an NC of degree n\geq 1, for short) is a construct

where

1. V is a finite alphabet;
2. w_{i}\in \left\langle V,\mathbb{N}_{\infty } \right\rangle , for all 1\leq i\leq n, is the multiset initially associated to cell i;
3. R is a finite set of interaction rules of the form \left( X\rightarrow Y;P,Q\right) where X=\left( x_{1},\dots ,x_{n}\right) , Y=\left( y_{1},\dots ,y_{n}\right) , x_{i},y_{i}\in \left\langle V,\mathbb{N}\right\rangle , 1\leq i\leq n, are vectors of multisets over V and P=\left( p_{1},\dots,p_{n}\right) , Q=\left( f_{1},\dots ,f_{n}\right) , p_{i},f_{i}, 1\leq i\leq n are finite sets of multisets over V.

We remark that in the definition given above w_{i} might be an infinite multiset. However, in most of the cases, only one cell, called the environment, will contain an infinite multiset. Hence we define Infinite(\Pi ) as the vector specifying the symbols with infinite multiplicity. More exactly,

Moreover, we define inf_{i}^{\prime }, 1\leq i\leq n, to be the infinite submultisets of w_{i} taking into account only the symbols with infinite multiplicity, i.e., f_{inf_{i}^{\prime }}\left( a\right) =\infty \ for f_{w_{i}}\left( a\right) =\infty \ and f_{inf_{i}^{\prime }}\left( a\right)=0 for f_{w_{i}}\left( a\right) <\infty , a\in V, as well as w_{i}^{\prime }, 1\leq i\leq n, to be the finite submultisets of w_{i} taking into account only the symbols with finite multiplicity, i.e., f_{w_{i}^{\prime }}\left( a\right) =0\ for f_{w_{i}}\left( a\right) =\infty \ and f_{w_{i}^{\prime }}\left( a\right) =f_{w_{i}}\left( a\right) \ for f_{w_{i}}\left( a\right) <\infty , a\in V.

We will also use the notation

for a rule \left( X\rightarrow Y;P,Q\right) . Moreover, if some p_{i} or f_{i} is an empty set or some x_{i} or y_{i} is equal to the empty multiset, 1\leq i\leq n, then we may omit it from the specification of the rule.

A network of cells consists of n cells, numbered from 1 to n, that contain (possibly infinite) multisets of objects over V; initially cell i contains multiset w_{i}. Cells can interact with each other by means of the rules in R. An interaction rule

rewrites objects x_{i} from cells i into objects y_{j} in cells j, 1\leq i,j\leq n if cells k, 1\leq k\leq n, contain all multisets from p_{k} and do not contain any multiset from f_{k}. In other words, the first part of the rule specifies the rewriting of symbols, the second part of the rule specifies permitting conditions and the third part of the rule specifies the forbidding conditions. In the next section we give a precise definition for the application of an interaction rule.

For an interaction rule r of the form above, the set

induces a relation between the interacting cells. However, this relation need not give rise to a structure relation like a tree as in P systems or a graph as in tissue P systems (e.g., see PaunBook02 for definitions of P systems and tissue P systems), though most models of membrane systems with a static membrane structure can be seen as special variants of NCs, and moreover, a lot of important features of membrane systems, in particular the derivation step and the halting condition, may be described at the level of NCs.