Further Results on Time-Free P Systems

Membrane systems (currently called P systems) are parallel computing devices inspired by the structure and the functioning of living cells. A standard feature of P systems is that each rule is executed in exactly one time unit. Actually in living cells different chemical reactions might take different times to be executed; moreover, it might be hard to know precisely such time of execution. For this reason, in [7] have been defined and investigated two models of P systems (time-free and clock-free P systems) where the time of execution of the rules is arbitrary and the output produced by the system is always the same, independently from such time. Preliminary results concerning time-free and clock-free P system have been obtained in [6, 7, 8]. In this paper we continue these investigations by considering different combinations of possible ingredients. In particular, we present the universality of time-free P systems using bi-stable catalysts. On the other, hand we prove that this implies that is not possible to decide whether an arbitrary bi-stable catalytic P system is time-free. We present several results about time-free evolution- communication P systems, where the computation is a mixed application of evolution and symport/antiport rules. In this case we obtain the universality even by using non-cooperative evolution rules and antiports of weight one. Finally, we formulate several open problems