We prove that arbitrary single-tape Turing machines can be simulated by uniform families of P systems with active membranes with a cubic slowdown and quadratic space overhead. This result is the culmination of a series of previous partial results, finally establishing the equivalence (up to a polynomial) of many space complexity classes defined in terms of P systems and Turing machines. The equivalence we obtained also allows a number of classic computational complexity theorems, such as Savitchʼs theorem and the space hierarchy theorem, to be directly translated into statements about membrane systems.

Alhazov, A., Leporati, A., Mauri, G., Porreca, A., Zandron, C. (2014). Space complexity equivalence of P systems with active membranes and Turing machines. THEORETICAL COMPUTER SCIENCE, 529, 69-81 [10.1016/j.tcs.2013.11.015].

Space complexity equivalence of P systems with active membranes and Turing machines

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

Abstract

We prove that arbitrary single-tape Turing machines can be simulated by uniform families of P systems with active membranes with a cubic slowdown and quadratic space overhead. This result is the culmination of a series of previous partial results, finally establishing the equivalence (up to a polynomial) of many space complexity classes defined in terms of P systems and Turing machines. The equivalence we obtained also allows a number of classic computational complexity theorems, such as Savitchʼs theorem and the space hierarchy theorem, to be directly translated into statements about membrane systems.
Articolo in rivista - Articolo scientifico
P systems with active membranes; Turing machines; Computational complexity
English
2014
529
69
81
none
Alhazov, A., Leporati, A., Mauri, G., Porreca, A., Zandron, C. (2014). Space complexity equivalence of P systems with active membranes and Turing machines. THEORETICAL COMPUTER SCIENCE, 529, 69-81 [10.1016/j.tcs.2013.11.015].
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/49328
Citazioni
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 20
Social impact