A Characterisation of NL Using Membrane Systems without Charges and Dissolution

DOI10.1007/978-3-540-85194-3_14zbMath1166.68327OpenAlexW1563879088MaRDI QIDQ3543341

Niall Murphy, Damien Woods

Publication date: 2 December 2008

Published in: Unconventional Computing (Search for Journal in Brave)

Full work available at URL: http://eprints.maynoothuniversity.ie/2366/1/NM_NUIM-CS-TR-2008-01.pdf

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

P colonies with agent division ⋮ On the power of membrane dissolution in polarizationless P systems with active membranes ⋮ A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules ⋮ Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes ⋮ A new method to simulate restricted variants of polarizationless P systems with active membranes

Cites Work

• Unnamed Item
• 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
• Membrane computing. An introduction.
• On uniformity within \(NC^ 1\)
• Parity, circuits, and the polynomial-time hierarchy
• Computational efficiency of dissolution rules in membrane systems
• Uniform Solution of QSAT Using Polarizationless Active Membranes
• Expressibility and Parallel Complexity
• Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P

This page was built for publication: A Characterisation of NL Using Membrane Systems without Charges and Dissolution