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.

Further Results on Time-Free P Systems

DEUFEMIA, Vincenzo
2006-01-01

Abstract

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/1636699
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 11
social impact