P systems with active membranes working in polynomial space

DOI10.1142/S0129054111007836MaRDI QIDQ3076598zbMATH OpenDBLPWikidataFDO

Authors Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron

Publication date 23 February 2011

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

complexity theorymembrane computingspace complexity

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• P systems with active membranes: Trading time for space
• A gap in the space hierarchy of P systems with active membranes
• Constant-space P systems with active membranes
• Bounding the space in P systems with active membranes
• P Systems with Active Membranes Characterize PSPACE

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• Complexity classes for membrane systems
• Complexity classes in models of cellular computing with membranes
• Membrane computing. 10th international workshop, WMC 2009, Curtea de Arges, Romania, August 24--27, 2009. Revised selected and invited papers
• Non-confluence in divisionless P systems with active membranes

Cited in

(27)

• Characterizing PSPACE with shallow non-confluent P systems
• A topology for P-systems with active membranes
• Further remark on P systems with active membranes and two polarizations
• On maximal parallel application of rules in rewriting P systems
• RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS
• Bounding the space in P systems with active membranes
• Alternative space definitions for P systems with active membranes
• Constant-space P systems with active membranes
• Space complexity equivalence of P systems with active membranes and Turing machines
• On a powerful class of non-universal P systems with active membranes
• Evaluating space measures in P systems
• Shallow non-confluent P systems
• A gap in the space hierarchy of P systems with active membranes
• Unconventional Computation
• P systems with active membranes: Trading time for space
• An efficient simulation of polynomial-space Turing machines by P systems with active membranes
• P Systems with Elementary Active Membranes: Beyond NP and coNP
• Monodirectional P systems
• scientific article; zbMATH DE number 6665229 (Why is no real title available?)
• Sublinear-space P systems with active membranes
• Machines, Computations, and Universality
• Active P-colonies
• P Systems with Active Membranes Working in Sublinear Space
• Membrane systems languages are polynomial-time parsable
• On the universality of P systems with membrane creation
• Coping with dynamical structures for interdisciplinary applications of membrane computing
• P Systems with Active Membranes Characterize PSPACE

This page was built for publication: P systems with active membranes working in polynomial space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3076598)