Π machines: virtual machines realizing graph structured transition P systems

摘要

P systems is a model of computation inspired by the way cells live and function. A typical P system consists of nested compartments surrounded by porous membranes, which contain data that are transformed by transformation rules. P systems can be simulated by a distributed computing system, where each compartment of a given system is simulated by a (remote) process, each running on a different node. By adopting a more "liberal" membrane structure where compartments do not necessarily form a tree-structure but a graph-structure, we get a more general model of computation, which we call graph structured P systems. Any instance of the new model can be implemented by a network of virtual machines, called &Pgr; machines, where each machine is able to implement the functionality of any simple compartment.