We prove that uniform and semi-uniform families of P systems with active membranes using only communication and nonelementary division rules are not computationally universal. However, they are powerful enough to solve exactly the problems solvable by Turing machines operating in time and space that are ”tetrational” (i.e., bounded by a stack of exponentials of polynomial height) with respect to the size of the input.

Porreca, A., Leporati, A., Zandron, C. (2010). On a Powerful Class of Non-universal P Systems with Active Membranes. In Developments in Language Theory (pp.364-375). Berlino : Springer-Verlag [10.1007/978-3-642-14455-4_33].

On a Powerful Class of Non-universal P Systems with Active Membranes

PORRECA, ANTONIO ENRICO;LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO
2010

Abstract

We prove that uniform and semi-uniform families of P systems with active membranes using only communication and nonelementary division rules are not computationally universal. However, they are powerful enough to solve exactly the problems solvable by Turing machines operating in time and space that are ”tetrational” (i.e., bounded by a stack of exponentials of polynomial height) with respect to the size of the input.
paper
Membrane computing, P systems, space complexity, tetrational space
English
Developments in Language Theory
2010
Developments in Language Theory
978-3-642-14454-7
2010
6224
364
375
none
Porreca, A., Leporati, A., Zandron, C. (2010). On a Powerful Class of Non-universal P Systems with Active Membranes. In Developments in Language Theory (pp.364-375). Berlino : Springer-Verlag [10.1007/978-3-642-14455-4_33].
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/43584
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
Social impact