Energy-based P systems have been recently introduced as P systems in which the amount of energy consumed and/or manipulated during computations is taken into account. In this paper we consider conservative computations performed by energy-based P systems, that is, computations for which the amount of energy entering the system is the same as the amount of energy leaving it. We show that conservative computations naturally allow to define an NP-hard optimization problem, here referred to as MIN STORAGE, and a corresponding NP-complete decision problem, CONSCOMP. Finally, we present a polynomial time 2-approximation algorithm for MIN STORAGE

Leporati, A., Zandron, C., Mauri, G. (2005). Conservative Computations in Energy-based P Systems. In Membrane Computing: 5th International Workshop (pp.344-358). Springer-Verlag [10.1007/978-3-540-31837-8_22].

Conservative Computations in Energy-based P Systems

LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO;MAURI, GIANCARLO
2005

Abstract

Energy-based P systems have been recently introduced as P systems in which the amount of energy consumed and/or manipulated during computations is taken into account. In this paper we consider conservative computations performed by energy-based P systems, that is, computations for which the amount of energy entering the system is the same as the amount of energy leaving it. We show that conservative computations naturally allow to define an NP-hard optimization problem, here referred to as MIN STORAGE, and a corresponding NP-complete decision problem, CONSCOMP. Finally, we present a polynomial time 2-approximation algorithm for MIN STORAGE
Conservative computations, energy-based P systems
English
5th International Workshop on Membrane Computing, WMC 2004
2004
Membrane Computing: 5th International Workshop
978-3-540-25080-7
2005
3365
344
358
none
Leporati, A., Zandron, C., Mauri, G. (2005). Conservative Computations in Energy-based P Systems. In Membrane Computing: 5th International Workshop (pp.344-358). Springer-Verlag [10.1007/978-3-540-31837-8_22].
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/10281/12017
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
Social impact