Search

We consider tissue P systems working on vesicles of multisets with the very simple operations of insertion, deletion, and substitution of single objects. With the whole multiset being enclosed in a vesicle, sending it to a target cell can be indicated in those simple rules working on the multiset. As derivation modes we consider the sequential mode, where exactly one rule is applied in a derivation step, and the set maximal mode, where in each derivation step a non-extendable set of rules is applied. With the set maximal mode, computational completeness can already be obtained with tissue P systems having a tree structure, whereas tissue P systems even with an arbitrary communication structure are not computationally complete when working in the sequential mode. Adding polarizations (-1, 0, 1 are sufficient) allows for obtaining computational completeness even for tissue P systems working in the sequential mode.

In this paper we focus on two weak forms of cooperation in P systems, namely, catalytic rules and matter/anti-matter annihilation rules. These variants of P systems both are computationally complete, while the corresponding rule complexity turns out to be of special interest. For establishing considerably small universal P systems in both cases, we found two suitable tools: generalized register machines and generalized counter automata. Depending on the features used in the different variants, we construct several small universal P systems.

We study cooperating distributed grammar systems working in hybrid modes in connection with the finite index restriction in two different ways: firstly, we investigate cooperating distributed grammar systems working in hybrid modes which characterize programmed grammars with the finite index restriction; looking at the number of components of such systems, we obtain surprisingly rich lattice structures for the inclusion relations between the corresponding language families. Secondly, we impose the finite index restriction on cooperating distributed grammar systems working in hybrid modes themselves, which leads us to new characterizations of programmed grammars of finite index.

Whether P systems with only one catalyst can already be computationally complete, is still an open problem. Here we establish computational completeness by using specific variants of additional control mechanisms. At each step using only multiset rewriting rules from one set of a finite number of sets of multiset rewriting rules allows for obtaining computational completeness with one catalyst and only one membrane. If the targets are used for choosing the multiset of rules to be applied, for getting computational completeness with only one catalyst more than one membrane is needed. If the available sets of rules change periodically with time, computational completeness can be obtained with one catalyst in one membrane. Moreover, we also improve existing computational completeness results for P systems with mobile catalysts and for P systems with membrane creation.

We consider the (one-dimensional) array counterpart of contextual as well as insertion and deletion string grammars and consider the operations of array insertion and deletion in array grammars. First we show that the emptiness problem for P systems with (one-dimensional) insertion rules is undecidable. Then we show computational completeness of P systems using (one-dimensional) array insertion and deletion rules even of norm one only. The main result of the paper exhibits computational completeness of one-dimensional array grammars using array insertion and deletion rules of norm at most two.

In this paper we study a notion of self-stabilization, inspired from biology and engineering. Multiple variants of formalization of this notion are considered, and we discuss how such properties affect the computational power of multiset rewriting systems.

In this article, we consider the operations of insertion and deletion working in a graph-controlled manner. We show that like in the case of context-free productions, the computational power is strictly increased when using a control graph: computational completeness can be obtained by systems with insertion or deletion rules involving at most two symbols in a contextual or in a context-free manner and with the control graph having only four nodes.

The operations drip and mate considered in (mem)brane computing resemble the operations cut and recombination well known from DNA computing. We here consider sets of vesicles with multisets of objects on their outside membrane interacting by drip and mate in two different setups: in test tube systems, the vesicles may pass from one tube to another one provided they fulfill specific constraints; in tissue-like P systems, the vesicles are immediately passed to specified cells after having undergone a drip or mate operation. In both variants, computational completeness can be obtained, yet with different constraints for the drip and mate operations.

We consider P systems with a linear membrane structure working on objects over a unary alphabet using sets of rules resembling homomorphisms. Such a restricted variant of P systems allows for a unique minimal representation of the generated unary language and in that way for an effective solution of the equivalence problem. Moreover, we examine the descriptional complexity of unary P systems with respect to the number of membranes.