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, Asynchronous P systems with active membranes, A toolbox for simpler active membrane algorithms, The counting power of P systems with antimatter, Subroutines in P systems and closure properties of their complexity classes, 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