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)

Full work available at URL https://doi.org/10.1142/S0129054111007836

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

• Complexity classes for membrane systems
• Complexity classes in models of cellular computing with membranes
• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• 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)

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

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)