We show that a deterministic single-tape Turing machine, operating in polynomial space with respect to the input length, can be efficiently simulated (both in terms of time and space) by a semi-uniform family of P systems with active membranes and three polarizations, using only communication rules. Then, basing upon this simulation, we prove that a result similar to the space hierarchy theorem can be obtained for P systems with active membranes: the larger the amount of space we can use during the computations, the harder the problems we are able to solve. © 2010 Springer-Verlag.

Valsecchi, A., Porreca, A., Leporati, A., Mauri, G., Zandron, C. (2010). An Efficient Simulation of Polynomial-Space Turing Machines by P Systems with Active Membranes. In Membrane Computing, 10th International Workshop, WMC10, Revised Selected and Invited Papers (pp.461-478). Springer-Verlag [10.1007/978-3-642-11467-0_31].

An Efficient Simulation of Polynomial-Space Turing Machines by P Systems with Active Membranes

VALSECCHI, ANDREA;PORRECA, ANTONIO ENRICO;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2010

Abstract

We show that a deterministic single-tape Turing machine, operating in polynomial space with respect to the input length, can be efficiently simulated (both in terms of time and space) by a semi-uniform family of P systems with active membranes and three polarizations, using only communication rules. Then, basing upon this simulation, we prove that a result similar to the space hierarchy theorem can be obtained for P systems with active membranes: the larger the amount of space we can use during the computations, the harder the problems we are able to solve. © 2010 Springer-Verlag.
slide + paper
Polynomial space; Turing machines; P systems with active membranes
English
10th International Workshop on Membrane Computing
2009
Membrane Computing, 10th International Workshop, WMC10, Revised Selected and Invited Papers
978-3-642-11466-3
2010
LNCS 5957
461
478
none
Valsecchi, A., Porreca, A., Leporati, A., Mauri, G., Zandron, C. (2010). An Efficient Simulation of Polynomial-Space Turing Machines by P Systems with Active Membranes. In Membrane Computing, 10th International Workshop, WMC10, Revised Selected and Invited Papers (pp.461-478). Springer-Verlag [10.1007/978-3-642-11467-0_31].
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/12009
Citazioni
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 4
Social impact