Energy plays an important role in many theoretical computational models. In this paper we review some results we have obtained in the last few years concerning the computational power of two variants of P systems that manipulate energy while performing their computations: energy-based and UREM P systems. In the former, a fixed amount of energy is associated to each object, and the rules transform objects by manipulating their energy. We show that if we assign local priorities to the rules, then energy-based P systems are as powerful as Turing machines, otherwise they can be simulated by vector addition systems and hence are not universal. We also discuss the simulation of conservative and reversible circuits of Fredkin gates by means of (self)-reversible energy-based P systems. On the other side, UREM P systems are membrane systems in which a given amount of energy is associated to each membrane. The rules transform and move single objects among the regions. When an object crosses a membrane, it may modify the associated energy value. Also in this case, we show that UREM P systems reach the power of Turing machines if we assign a sort of local priorities to the rules, whereas without priorities they characterize the class PsMAT λ, and hence are not universal. © 2010 Springer-Verlag.
Mauri, G., Leporati, A., Zandron, C. (2010). Energy-based Models of P systems. In Membrane Computing, 10th International Workshop, WMC10, Revised Selected and Invited Papers (pp.104-124). Springer-Verlag [10.1007/978-3-642-11467-0_9].
Energy-based Models of P systems
MAURI, GIANCARLO;LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO
2010
Abstract
Energy plays an important role in many theoretical computational models. In this paper we review some results we have obtained in the last few years concerning the computational power of two variants of P systems that manipulate energy while performing their computations: energy-based and UREM P systems. In the former, a fixed amount of energy is associated to each object, and the rules transform objects by manipulating their energy. We show that if we assign local priorities to the rules, then energy-based P systems are as powerful as Turing machines, otherwise they can be simulated by vector addition systems and hence are not universal. We also discuss the simulation of conservative and reversible circuits of Fredkin gates by means of (self)-reversible energy-based P systems. On the other side, UREM P systems are membrane systems in which a given amount of energy is associated to each membrane. The rules transform and move single objects among the regions. When an object crosses a membrane, it may modify the associated energy value. Also in this case, we show that UREM P systems reach the power of Turing machines if we assign a sort of local priorities to the rules, whereas without priorities they characterize the class PsMAT λ, and hence are not universal. © 2010 Springer-Verlag.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
