Characterizing PSPACE with shallow non-confluent P systems

DOI10.1007/S41965-019-00011-4zbMATH Open1431.68030arXiv1902.09523OpenAlexW3100234586WikidataQ128058025 ScholiaQ128058025MaRDI QIDQ2299883FDOQ2299883

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

Publication date: 24 February 2020

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

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.

Full work available at URL: https://arxiv.org/abs/1902.09523

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

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)

Cites Work

• Title not available (Why is that?)
• The computational power of cell division in P systems: Beating down parallel computers?
• Membrane computing and complexity theory: A characterization of PSPACE
• Title not available (Why is that?)
• Complexity classes in models of cellular computing with membranes
• Recent complexity-theoretic results on P systems with active membranes
• The computational power of membrane systems under tight uniformity conditions
• Membrane division, oracles, and the counting hierarchy
• Simulating Elementary Active Membranes
• A toolbox for simpler active membrane algorithms
• Characterising the complexity of tissue P systems with fission rules
• Subroutines in P systems and closure properties of their complexity classes
• Non-confluence in divisionless P systems with active membranes
• The counting power of P systems with antimatter
• Monodirectional P systems
• Solving QSAT in sublinear depth
• Shallow Non-confluent P Systems

Cited In (11)

• 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
• On maximal parallel application of rules in rewriting P systems
• Solving a PSPACE-complete problem with cP 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)