The computational power of membrane systems under tight uniformity conditions

DOI10.1007/S11047-010-9244-7MaRDI QIDQ537860zbMATH OpenOpenAlexFDO

Authors Niall Murphy, Damien Woods

Publication date 23 May 2011

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL http://mural.maynoothuniversity.ie/12412/1/Woods_Computational_2011.pdf

zbMATH Keywords

computational complexityuniformitymembrane systemsNLP-systemssemi-uniformity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A Characterisation of NL Using Membrane Systems without Charges and Dissolution
• Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems
• On a powerful class of non-universal P systems with active membranes
• Complexity classes for membrane systems: a survey
• Sublinear-space P systems with active membranes

Cites work

• scientific article; zbMATH DE number 1583885 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 549851 (Why is no real title available?)
• scientific article; zbMATH DE number 2080946 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Complexity classes in models of cellular computing with membranes
• Computational efficiency of dissolution rules in membrane systems
• Expressibility and Parallel Complexity
• Membrane computing and complexity theory: A characterization of PSPACE
• Nondeterministic Space is Closed under Complementation
• On uniformity within \(NC^ 1\)
• P systems with active membranes: Attacking NP-complete problems
• Uniform Solution of QSAT Using Polarizationless Active Membranes

Cited in

(27)

• A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules
• Characterizing PSPACE with shallow non-confluent P systems
• P systems attacking hard problems beyond NP: a survey
• Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems
• Subroutines in P systems and closure properties of their complexity classes
• A new method to simulate restricted variants of polarizationless P systems with active membranes
• Asynchronous P systems with active membranes
• RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS
• A Turing machine simulation by P systems without charges
• Bounding the space in P systems with active membranes
• Alternative space definitions for P systems with active membranes
• Simulating counting oracles with cooperation
• Shallow laconic P-systems can count
• Depth-two P systems can simulate Turing machines with \textbf{NP} oracles
• Space complexity equivalence of P systems with active membranes and Turing machines
• On the power of P systems with active membranes using weak non-elementary membrane division
• Evaluating space measures in P systems
• Characterising the complexity of tissue P systems with fission rules
• P systems simulating oracle computations
• Remarks on the computational power of some restricted variants of P systems with active membranes
• Shallow non-confluent P systems
• The counting power of P systems with antimatter
• Monodirectional P systems
• Low-order continualization of an anisotropic membrane lattice with next-nearest interactions. Enhanced prediction of its dynamic behaviour
• A toolbox for simpler active membrane algorithms
• Predictors for flat membrane systems
• On the Computational Power of Flip-Flop Proteins on Membranes

This page was built for publication: The computational power of membrane systems under tight uniformity conditions

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