P systems with active membranes: Trading time for space

DOI10.1007/S11047-010-9189-XMaRDI QIDQ537818zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 23 May 2011

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11047-010-9189-x

zbMATH Keywords

computational complexitymembrane computingregister machines

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• P systems with active membranes working in polynomial space
• Further remark on P systems with active membranes and two polarizations
• Solution to PSPACE-complete problem using P systems with active membranes with time-freeness
• Further remarks on \(P\) systems with active membranes, separation, merging, and release rules
• Membrane Computing

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1735636 (Why is no real title available?)
• scientific article; zbMATH DE number 2080946 (Why is no real title available?)
• scientific article; zbMATH DE number 1738664 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• A polynomial complexity class in P systems using membrane division
• Aspects of Molecular Computing
• Computing with membranes
• From regulated rewriting to computing with membranes: collapsing hierarchies
• Membrane Computing
• Membrane Computing
• P systems with active membranes: Attacking NP-complete problems
• The computational power of cell division in P systems: Beating down parallel computers?

Cited in

(11)

• Polymorphic P Systems with Non-cooperative Rules and No Ingredients
• scientific article; zbMATH DE number 2118901 (Why is no real title available?)
• On maximal parallel application of rules in rewriting P systems
• Bounding the space in P systems with active membranes
• Alternative space definitions for P systems with active membranes
• Evaluating space measures in P systems
• Trading polarizations for labels in P systems with active membranes
• Active P-colonies
• P Systems with Active Membranes Working in Sublinear Space
• P systems with active membranes working in polynomial space
• A linear time complexity of breadth-first search using P system with membrane division

This page was built for publication: P systems with active membranes: Trading time for space

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