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.
