A limitation of cell division in tissue P systems by PSPACE

DOI10.1016/J.JCSS.2014.10.006zbMATH Open1435.68099OpenAlexW2068184402MaRDI QIDQ473203FDOQ473203

Authors: Petr Sosík, Luděk Cienciala 

Publication date: 24 November 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.10.006

Recommendations

• Limits of the power of tissue P systems with cell division
• Tissue P systems with cell separation: upper bound by PSPACE
• Computational power of cell separation in tissue P systems
• Computational complexity of tissue-like P systems
• Tissue P systems with cell separation: attacking the partition problem

zbMATH Keywords

computational complexitymembrane computingcell divisionPSPACEtissue P-system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites Work

• Computing with membranes
• Title not available (Why is that?)
• Tissue P systems.
• Cell communication in tissue \(P\) systems: universality results
• A polynomial complexity class in P systems using membrane division
• Characterizing tractability by tissue-like P systems
• Computational complexity of tissue-like P systems
• Tissue P systems with channel states
• P systems with active membranes: Attacking NP-complete problems
• A computational complexity theory in membrane computing
• Membrane computing and complexity theory: A characterization of PSPACE
• Complexity classes in models of cellular computing with membranes
• P systems simulating oracle computations
• Title not available (Why is that?)
• Tissue P systems with cell separation: upper bound by PSPACE
• Title not available (Why is that?)
• Sublinear-space P systems with active membranes
• Developments in Language Theory

Cited In (7)

• The computational power of cell division in P systems: Beating down parallel computers?
• A polynomial alternative to unbounded environment for tissue P systems with cell division
• Limits of the power of tissue P systems with cell division
• Cell-like P systems with polarizations and minimal rules
• Characterising the complexity of tissue P systems with fission rules
• A uniform solution to SAT problem by symport/antiport P systems with channel states and membrane division
• Tissue P systems with cell separation: upper bound by PSPACE

This page was built for publication: A limitation of cell division in tissue P systems by PSPACE

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