A limitation of cell division in tissue P systems by PSPACE

DOI10.1016/J.JCSS.2014.10.006MaRDI QIDQ473203zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(9)

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

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)