Computational complexity of tissue-like P systems

DOI10.1016/J.JCO.2010.03.001MaRDI QIDQ983185zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1583871 (Why is no real title available?)
• scientific article; zbMATH DE number 1583885 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (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 CHARACTERIZATION OF PARIKH SETS OF ET0L LANGUAGES IN TERMS OF P SYSTEMS
• A polynomial complexity class in P systems using membrane division
• Aspects of Molecular Computing
• Cell communication in tissue \(P\) systems: universality results
• Computing with cells. Advances in membrane computing.
• Computing with membranes
• Developments in Language Theory
• Membrane Computing
• Membrane Computing
• Membrane computing. An introduction.
• Spiking neural P systems
• The power of communication: P systems with symport/antiport
• Tissue P systems with channel states
• Tissue P systems.

Cited in

(49)

• Shallow non-confluent P systems
• 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
• The computational complexity of tissue P systems with evolutional symport/antiport rules
• Solving the SAT problem by cell-like P systems with channel states and symport rules
• Computing with viruses
• Time-free solution to SAT problem by tissue P systems
• A bibliometric analysis of membrane computing (1998--2019)
• P systems with symport/antiport rules: when do the surroundings matter?
• A uniform solution to the independent set problem through tissue P systems with cell separation
• Tissue P systems with evolutional communication rules with two objects in the left-hand side
• 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
• Seeking computational efficiency boundaries: the Păun's conjecture
• A computational complexity theory in membrane computing
• 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 linear time complexity of breadth-first search using P system with membrane division
• A time-free uniform solution to subset sum problem by tissue P systems with cell division
• Tissue P systems with cell separation: attacking the partition problem
• 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
• 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
• Membrane fission versus cell division: when membrane proliferation is not enough
• Characterising the complexity of tissue P systems with fission rules
• 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
• Solving the 3-COL problem by using tissue P systems without environment and proteins on cells
• Homeostasis tissue-like P systems with cell separation
• 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
• scientific article; zbMATH DE number 2182416 (Why is no real title available?)
• The computational power of timed P systems with active membranes using promoters

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)