Abstract of Paper

Characterizations of Catalytic Membrane Computing Systems
by Oscar H. Ibarra, Zhe Dang, Omer Egecioglu and Gaurav Saxena

Abstract:

We look at 1-region membrane computing systems which only use rules of the
form Ca -> Cv, where C is a catalyst, a is a noncatalyst, and v is a
(possibly null) string of noncatalysts.  There are no rules of the form
a -> v. Thus, we can think of these systems as ``purely'' catalytic.
We consider two types: (1) when the initial configuration contains only one
catalyst, and (2) when the initial configuration contains multiple (not
necessarily distinct) catalysts.  We show that systems of the first type are
equivalent to communication-free Petri nets, which are also equivalent to
commutative context-free grammars.  They define precisely the semilinear sets.
This partially answers an open question in [19].  Systems of the second type
define exactly the recursively enumerable sets of tuples (i.e., Turing machine
computable).  We also study an extended model where the rules are of the
form q: (p, Ca -> Cv) (where q and p are states), i.e., the application of
the rules is guided by a finite-state control. For this generalized model,
type (a) as well as type (b) with some restriction correspond to vector
addition systems.