*For the most recent entries see the
Petri Nets Newsletter.*

## Catalytic P systems, semilinear sets, and vector addition systems.

Ibarra, Oscar H.;
Dangb, Zhe;
Egecioglu, Omer
In:
*Theoretical Computer Science, Volume 312, Issues 2-3 , 30 January 2004*, pages 379-399.
Elsevier,
January 2004.

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 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: WMC-CdeA'02, Lecture
Notes in Computer Science, vol. 2597, Springer, Berlin, 2003, pp. 400-409;
Computationally universal P systems without priorities: two catalysts are
sufficient, available at `http://psystems.disco.unimib.it,`
2003). 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 (1) as well as type
(2) with some restriction correspond to vector addition systems. Finally,
we briefly investigate the closure properties of catalytic systems.

Keywords:
Membrane computing; Catalytic system; Semilinear set; Vector addition
system; Reachability problem.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*