We prove that all-parallel enzymatic numerical P systems whose production functions can be expressed as a combination of sums, differences, products and integer divisions characterise PSPACE when working in polynomial time. We also show that, when only sums and differences are available, exactly the problems in P can be solved in polynomial time. These results are proved by showing how EN P systems and random access machines, running in polynomial time and using the same basic operations, can simulate each other efficiently.

Leporati, A., Mauri, G., Porreca, A., Zandron, C. (2014). Enzymatic Numerical P Systems Using Elementary Arithmetic Operations. In CMC 2013 – 14th International Conference on Membrane Computing, Revised Selected Papers (pp.249-264). Springer [10.1007/978-3-642-54239-8_18].

Enzymatic Numerical P Systems Using Elementary Arithmetic Operations

LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO;ZANDRON, CLAUDIO
2014

Abstract

We prove that all-parallel enzymatic numerical P systems whose production functions can be expressed as a combination of sums, differences, products and integer divisions characterise PSPACE when working in polynomial time. We also show that, when only sums and differences are available, exactly the problems in P can be solved in polynomial time. These results are proved by showing how EN P systems and random access machines, running in polynomial time and using the same basic operations, can simulate each other efficiently.
slide + paper
enzymatic P systems, PSPACE
English
International Conference on Membrane Computing
2013
Alhazov, A; Cojocaru, S; Gheorghe, M; Rogozhin, Y
CMC 2013 – 14th International Conference on Membrane Computing, Revised Selected Papers
978-3-642-54238-1
2014
8340
249
264
none
Leporati, A., Mauri, G., Porreca, A., Zandron, C. (2014). Enzymatic Numerical P Systems Using Elementary Arithmetic Operations. In CMC 2013 – 14th International Conference on Membrane Computing, Revised Selected Papers (pp.249-264). Springer [10.1007/978-3-642-54239-8_18].
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/50732
Citazioni
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
Social impact