Computational complexity of tissue-like P systems

DOI10.1016/J.JCO.2010.03.001zbMATH Open1195.68050OpenAlexW2065714916MaRDI QIDQ983185FDOQ983185

Authors: Mario J. Pérez-Jiménez, Linqiang Pan 

Publication date: 3 August 2010

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2010.03.001

Recommendations

• The computational complexity of tissue P systems with evolutional symport/antiport rules
• An optimal frontier of the efficiency of tissue P systems with cell separation
• Tissue P systems with cell separation: attacking the partition problem
• Computational power of cell separation in tissue P systems
• Tissue P systems with cell separation: upper bound by PSPACE

zbMATH Keywords

membrane computingSATcell separationtissue P systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cites Work

• Title not available (Why is that?)
• Computing with membranes
• Membrane computing. An introduction.
• Tissue P systems.
• Cell communication in tissue \(P\) systems: universality results
• A polynomial complexity class in P systems using membrane division
• Spiking neural P systems
• The power of communication: P systems with symport/antiport
• Tissue P systems with channel states
• Computing with cells. Advances in membrane computing.
• Title not available (Why is that?)
• Membrane Computing
• Title not available (Why is that?)
• Title not available (Why is that?)
• Developments in Language Theory
• Membrane Computing
• Aspects of Molecular Computing
• Title not available (Why is that?)
• A CHARACTERIZATION OF PARIKH SETS OF ET0L LANGUAGES IN TERMS OF P SYSTEMS

Cited In (49)

• Tissue P systems with promoter simulation with MeCoSim and P-Lingua framework
• The computational power of cell-like P systems with one protein on membrane
• Solving the SAT problem by cell-like P systems with channel states and symport rules
• The computational complexity of tissue P systems with evolutional symport/antiport rules
• A bibliometric analysis of membrane computing (1998--2019)
• Computing with viruses
• Time-free solution to SAT problem by tissue P systems
• P systems with symport/antiport rules: when do the surroundings matter?
• Tissue P systems with evolutional communication rules with two objects in the left-hand side
• A uniform solution to the independent set problem through tissue P systems with cell separation
• Simple neural-like P systems for maximal independent set selection
• The computational power of monodirectional tissue P systems with symport rules
• A tissue P system based solution to quadratic assignment problem
• Towards automated deduction in cP systems
• A computational complexity theory in membrane computing
• Seeking computational efficiency boundaries: the Păun's conjecture
• An efficient time-free solution to SAT problem by P systems with proteins on membranes
• Probabilistic Guarded P Systems, A New Formal Modelling Framework
• The computational power of tissue-like P systems with promoters
• Rule synchronization for tissue P systems
• Characterizing tractability by tissue-like P systems
• Monodirectional tissue P systems with channel states
• A time-free uniform solution to subset sum problem by tissue P systems with cell division
• A linear time complexity of breadth-first search using P system with membrane division
• Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division
• An efficient time-free solution to QSAT problem using P systems with proteins on membranes
• Tissue P systems with cell separation: attacking the partition problem
• A path to computational efficiency through membrane computing
• Cell-like P systems with polarizations and minimal rules
• Tissue-like P systems with evolutional symport/antiport rules
• Characterising the complexity of tissue P systems with fission rules
• Membrane fission versus cell division: when membrane proliferation is not enough
• Efficient simulation of tissue-like P systems by transition cell-like P systems
• TISSUE-LIKE P SYSTEMS WITH DYNAMICALLY EMERGING REQUESTS
• A limitation of cell division in tissue P systems by PSPACE
• RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS
• A uniform solution to SAT problem by symport/antiport P systems with channel states and membrane division
• On the efficiency of cell-like and tissue-like recognizing membrane systems
• Descriptional Complexity of Tissue-Like P Systems with Cell Division
• Homeostasis tissue-like P systems with cell separation
• Solving the 3-COL problem by using tissue P systems without environment and proteins on cells
• A uniform family of tissue P systems with protein on cells solving 3-coloring in linear time
• Computational complexity of simple P systems
• Computational power of cell separation in tissue P systems
• Computational power of tissue P systems for generating control languages
• Tissue P systems with cell separation: upper bound by PSPACE
• Title not available (Why is that?)
• The computational power of timed P systems with active membranes using promoters
• Shallow non-confluent P systems

This page was built for publication: Computational complexity of tissue-like P systems

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