The computational power of membrane systems under tight uniformity conditions

DOI10.1007/s11047-010-9244-7zbMath1214.68159OpenAlexW1986546859MaRDI 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 complexityuniformitymembrane systemsNLP-systemssemi-uniformity

Mathematics Subject Classification ID

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

Related Items (23)

P Systems Simulating Oracle Computations ⋮ On the power of P systems with active membranes using weak non-elementary membrane division ⋮ Characterising the complexity of tissue P systems with fission rules ⋮ The counting power of P systems with antimatter ⋮ Asynchronous P systems with active membranes ⋮ A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules ⋮ Evaluating space measures in P systems ⋮ Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes ⋮ Shallow Non-confluent P Systems ⋮ Space complexity equivalence of P systems with active membranes and Turing machines ⋮ 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 ⋮ RESEARCH FRONTIERS OF MEMBRANE COMPUTING: OPEN PROBLEMS AND RESEARCH TOPICS ⋮ A toolbox for simpler active membrane algorithms ⋮ 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 ⋮ Depth-two P systems can simulate Turing machines with \textbf{NP} oracles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

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