Computing with Membranes: P Systems with Worm-Objects

Abstract

We consider a combination of P systems with objects described by symbols with P systems with objects described by strings. Namely, we work with multisets of strings and consider as the result of a computation the number of strings in a given output membrane. The strings (also called worms) are processed by replication, splitting, mutation, and recombination; no priority among rules and no other ingredient is used. In these circumstances, it is proved that (1) P systems of this type can generate all recursively enumerable sets of numbers, and, moreover, (2) the Hamiltonian Path Problem in a directed graph can be solved in a quadratic time, while the SAT problem can be solved in a linear time.