The computational power of membrane systems under tight uniformity conditions

DOI10.1007/s11047-010-9244-7zbMath1214.68159MaRDI QIDQ537860

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 complexity; uniformity; membrane systems; NL; P-systems; semi-uniformity

Mathematics Subject Classification ID

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

Related Items

RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS, A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules, Evaluating space measures in P systems, Asynchronous P systems with active membranes, A toolbox for simpler active membrane algorithms, The counting power of P systems with antimatter, A Turing machine simulation by P systems without charges, Bounding the space in P systems with active membranes, Simulating counting oracles with cooperation, Alternative space definitions for P systems with active membranes, Shallow laconic P-systems can count, A new method to simulate restricted variants of polarizationless P systems with active membranes, Depth-two P systems can simulate Turing machines with \textbf{NP} oracles, On the power of P systems with active membranes using weak non-elementary membrane division, Subroutines in P systems and closure properties of their complexity classes, Characterizing PSPACE with shallow non-confluent P systems, P systems attacking hard problems beyond NP: a survey, Monodirectional P systems, Characterising the complexity of tissue P systems with fission rules, Space complexity equivalence of P systems with active membranes and Turing machines, 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

Cites Work

• Membrane computing and complexity theory: A characterization of PSPACE
• Complexity classes in models of cellular computing with membranes
• On uniformity within \(NC^ 1\)
• Computational efficiency of dissolution rules in membrane systems
• Uniform Solution of QSAT Using Polarizationless Active Membranes
• Nondeterministic Space is Closed under Complementation
• Expressibility and Parallel Complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item