Characterizing PSPACE with shallow non-confluent P systems

DOI10.1007/S41965-019-00011-4MaRDI QIDQ2299883zbMATH OpenOpenAlexWikidataFDO

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

Publication date 24 February 2020

Published in Journal of Membrane Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.09523, https://idus.us.es/xmlui/handle//11441/84092

zbMATH Keywords

PSPACEactive membranesP-systemsnon-confluent

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Abstract: In P systems with active membranes, the question of understanding the power of non-confluence within a polynomial time bound is still an open problem. It is known that, for shallow P systems, that is, with only one level of nesting, non-confluence allows them to solve conjecturally harder problems than confluent P systems, thus reaching PSPACE. Here we show that PSPACE is not only a bound, but actually an exact characterization. Therefore, the power endowed by non-confluence to shallow P systems is equal to the power gained by confluent P systems when non-elementary membrane division and polynomial depth are allowed, thus suggesting a connection between the roles of non-confluence and nesting depth.

Recommendations

• Shallow non-confluent P systems
• Non-confluence in divisionless P systems with active membranes
• P systems with active membranes working in polynomial space
• On the power of P systems with active membranes using weak non-elementary membrane division
• scientific article; zbMATH DE number 6665229

Cites work

• scientific article; zbMATH DE number 1583885 (Why is no real title available?)
• scientific article; zbMATH DE number 5671765 (Why is no real title available?)
• A toolbox for simpler active membrane algorithms
• Characterising the complexity of tissue P systems with fission rules
• Complexity classes in models of cellular computing with membranes
• Membrane computing and complexity theory: A characterization of PSPACE
• Membrane division, oracles, and the counting hierarchy
• Monodirectional P systems
• Non-confluence in divisionless P systems with active membranes
• Recent complexity-theoretic results on P systems with active membranes
• Shallow non-confluent P systems
• Simulating elementary active membranes
• Solving QSAT in sublinear depth
• Subroutines in P systems and closure properties of their complexity classes
• The computational power of cell division in P systems: Beating down parallel computers?
• The computational power of membrane systems under tight uniformity conditions
• The counting power of P systems with antimatter

Cited in

(12)

• Shallow non-confluent P systems
• Bounding the space in P systems with active membranes
• Alternative space definitions for P systems with active membranes
• A bibliometric analysis of membrane computing (1998--2019)
• Proof techniques in membrane computing
• Active P-colonies
• Solving a PSPACE-complete problem with cP systems
• On maximal parallel application of rules in rewriting P systems
• Evaluating space measures in P systems
• On the power of P systems with active membranes using weak non-elementary membrane division
• Cell-like P systems with polarizations and minimal rules
• Spiking neural P systems with polarizations and rules on synapses

This page was built for publication: Characterizing PSPACE with shallow non-confluent P systems

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