Membrane systems and their dynamics

Membrane systems are models for the nondeterministic application of localized rewriting rules on finite sets of objects in a spatial hierarchy of so-called membranes. Time in these models advances in finite steps, such that they are special cases of nondeterministic discrete dynamical systems, or more exactly, of set-valued Markovian difference equations with countable state space. Membrane systems can also be considered as set-valued cellular automata with a countable, instead of a finite, number of states and a nontrivial topology, i.e. cellular automata on a tree. One can distinguish three kinds of possible rules. First there are rules for the conversion of objects inside a membrane. Second, there are rules for the transport of objects between membranes, from one level in the hierarchy to an adjoining membrane. Third, there are rules which allow for the dissolution of a membrane, such that the tree and the hierarchy it represents can dynamically change.
References
  1. Paun, G.: Computing with Membranes, J. Comput. Syst. Sci. 61 (2000), 108-143. [Seminal article that introduces membrane systems]
  2. Paun, G.: Membrane Computing: An Introduction. Springer, 2002. [Textbook]
  3. Muskulus, M.; et.al.: Cycles and communicating classes in membrane systems and molecular dynamics, Theoret. Comp. Sci. 372 (2007), 242-266.

Nondeterminism and maximal parallelism

The evolution of membrane systems is defined to be nondeterministic and maximally parallel. This means that the objects in each membrane evolve independently from each other, and in such a way that a maximal possible number of rules is used in each time step. The latter means, that for each membrane a sequence of rules is used, where no further rule can be added. The (finite) set of all possible such rule sequences are the admissible local state changes of the membrane under consideration. Mathematically, we consider two possibilities to deal with these notions of nondeterminism and maximal parallelism. On the one hand, one can study the evolution of membrane systems in a set-valued setting, where it becomes deterministic. On the other hand, one can study these systems in a probabilistic setting, where at each time step one of the possible admissible rule sequences is chosen randomly.

Probabilistic membrane systems

In the probabilistic setting, state changes need to be ruled by a probability law. The most interesting possibility is to use a law based on a physically/biologically realistic situation, i.e. probabilistic mass-action kinetics, where membranes are thought of as well-mixed reaction volumes in which the objects undergo stochastic chemical reactions with waiting times inversely proportional to the relative concentrations of objects in a membrane. The simplest case then is to consider sequential evolution, where at each time step only one rule in one membrane is executed. Note that we have two notions of time now: First the discrete (virtual) "time" steps of the membrane system evolution, secondly the continuous time of the chemical reality these describe. These models are special classes of so-called jump Markov models, whose trajectories converge, in a certain limit, to solutions of a system of ordinary differential equations. Although the theory has been studied for a long time, many interesting questions are still open.
References
  1. Pescini, D.; et.al.: Dynamical Probabilistic P Systems, Int. J. Found. Comp. Sci. 17 (2006), 183-204. [Introduces membrane systems in a probabilistic setting]
  2. Kurtz, T.G.: Solutions of Ordinary Differential Equations as Limits of Pure Jump Markov Processes, J. Appl. Prob. 7 (1970), 49-58.

Membrane systems and dynamical systems

Membrane system models work with a countable, discrete state space. A state is given by the number of objects in each membrane, i.e. it is a collection of multisets of objects, one for each membrane. By a simple argument ("collapsing the hierarchy"), these models are equivalent to membrane systems with one reaction volume (and additional objects, in general). Since state space is discrete, the usual methods of dynamical systems theory, which mainly deals with continuous state spaces, cannot be applied, or have to be modified accordingly. Many complications do not arise in such a setting. For example, the large-time behaviour of dynamical systems can be very complicated, such that the asymptotically approached sets of states, called attractors, can have a complicated, fractal structure. In the case of membrane systems, the only possibility are limit cycles, i.e. periodic trajectories. Therefore, state space can be partitioned into periodic trajectories and their basins of attraction, i.e. transient states which cannot be reached by evolution, and can only occur as initial conditions. These are called Garden of Eden configurations in the theory of cellular automata.
References
  1. Muskulus, M.; Brijder, R.: First Steps towards a Geometry of Computation. In: Third Brainstorming Week on Membrane Computing, eds.: Gutierrez-Naranjo, M.A.; et.al. Fenix Editora (2005). [Collapsing the hierarchies argument]

Symbolic dynamics

References
  1. Lind, D.; Marcus, B.: An Introduction to Symbolic Dynamis and Coding. Cambridge University Press (1995). [Standard reference, more on the applied side]
  2. Kitchens, B.P.: Symbolic Dynamics. Springer (2007). [Standard reference, more on the algebraic side]
  3. Muskulus, M.; Brijder, R.: Complexity of Biocomputation: Symbolic Dynamics in Membrane Systems, Int. J. Found. Comp. Sci. 17 (2006), 147-165. [An approach towards symbolic dynamics of membrane systems]

Markov chain theory

Stochastic Chemical Kinetics

References
  1. McQuarrie, D.A.: Stochastic Approach to Chemical Kinetics, J. Appl. Prob. 4 (1967), 413-478. [Review article]
  2. Bharucha-Reid, A.T.: Elements of the Theory of Markov Processes and their Applications. Dover (1988) [Standard reference; chapter 8 considers applications in chemistry]

Chemical reaction network theory I: Metabolic Control Theory

Chemical reaction network theory II: The linear algebra of complexes

Chemical reaction network theory III: Graph-theoretic Systems Biology

Michael Muskulus
Last modified: Thu Mar 15 20:16:43 CET 2007