Volume: 22, Issue: 1(2011)
pp. 65-73 DOI: 10.1142/S0129054111007836
|
|
Abstract |
Full Text (PDF, 192KB)
|
References
|
 |
| Title: |
P SYSTEMS WITH ACTIVE MEMBRANES WORKING IN POLYNOMIAL SPACE |
| Author(s): |
ANTONIO E. PORRECA
Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, ItalyALBERTO LEPORATI
Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, ItalyGIANCARLO MAURI
Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, ItalyCLAUDIO ZANDRON
Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy
|
| History: |
Received 18 June 2010
Accepted 1 October 2010
|
| Abstract: |
We prove that recognizer P systems with active membranes using polynomial space characterize the complexity class PSPACE. This result holds for both confluent and nonconfluent systems, and independently of the use of membrane division rules. |
| Keywords: |
Membrane computing; complexity theory; space complexity
AMSC numbers:
68Q10, 68Q15
|
|
|
