• CLS
• multiset rewriting
• P-Systems
• Gillespie
• string multiset rewriting
• system biology

In the last few years many formalisms, originally developed by
computer scientists to model systems of interacting components,
have been applied to Biology. Moreover, some
new formalisms have been proposed to describe biomolecular and membrane
interactions. All these formalisms can describe
biological systems at different levels of abstraction.

The first advantage of using formal models to describe biological systems is
that they avoid ambiguities. In fact, ambiguity is often a problem of the
notations used by biologists. Moreover, the formal modeling of biological
systems allows the development of simulators, which can be used to
understand how the described system behaves in normal conditions, and how
it reacts to changes in the environment and to alterations of some of its
components. Furthermore, formal models allow the verification of properties of
the described systems, by means of tools (such as model checkers) which are
well established and widely used in other application fields of Computer
Science, but unknown to biologists. It must be noticed that the development
of simulators for these formalisms may not be easy, in particular
also the definition of a stochastic semantics for those formalisms
may not be trivial.

In this thesis we propose an extension of multiset rewriting,
called \emph{String MultiSet Rewriting (SMSR)}, in which multiset
elements are strings and left hand sides of rewrite rules may
contain an operator, called maximal matching operator, which
allows representing the multiset of all strings having a common
given prefix.

SMSR can be used as an intermediate language for simulation
of higher level languages; here with the term high we refer to their
ability of describing biological systems at different level of abstraction.
On the one end, it is easy to develop simulators for SMSR, for
instance by extending the GBS simulator. On the other
hand, the maximal matching operator facilitates the translation of
higher level languages, in particular those based on term
rewriting. The idea is that a term can be seen as a tree, a tree
can be seen as a set of strings representing all paths from root
to leaves, and the replacement of a subtree becomes the replacement
of a set of strings having a common prefix. As an example we
start giving intuitions on the encoding of P-Systems
and then we show how a formalism based on term rewriting, CLS+,
can be translated into SMSR, and prove translation correctness and
completeness.

Higher level formalisms could be translated into
SMSR directly or via their translation into CLS+.
In both cases one would have the possibility of using the simulator
for SMSR to simulate high level descriptions.