Abstract:
P systems/membrane computing is a parallel and distributed model of computation.
This thesis focuses on two recently proposed P system variants: P systems with
complex objects (cP systems) and water-based P system (wP system).
This thesis rst investigates what can be computed utilising a single cP system cell.
We show for the rst time that cP systems can solve PSPACE complete problems in
polynomial time (linear). We will also, demonstrate the advantages of our solution
compared to other P system variants. Following this positive result, we demonstrate
e cient solutions to NP-complete problems surpassing previous results.
The thesis then looks at a P system model of water computing. We prove that this
model is Turing complete via the construction of recursive functions. Following this
construction, we demonstrate how this model can be viewed as a restricted cP system.
We then prove that this model can construct a PRAM machine. This construction
proves that the model can be used as an e cient parallel machine.
Finally, the thesis looks at using cP systems for solving distributed computing problems.
We rst solve the Byzantine agreement problem using newly proposed actor
based controls on the messages. We show that this new solution surpasses the previous
solutions in terms of: number of cells, number of steps, rule set size, and many
more. We then solve the Santa Claus problem demonstrating the usefulness of cP
systems as a concurrency speci cation language. We demonstrate the reduction of
program size of our cP solution compared to similar solutions implemented in modern
programming languages.