A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules

DOI10.1016/J.TCS.2023.113974zbMATH Open1512.68094OpenAlexW4378190111MaRDI QIDQ6162071FDOQ6162071

Authors: Zsolt Gazdag, Károly Hajagos 

Publication date: 15 June 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113974

Recommendations

• Unconventional Computation
• Sublinear-space P systems with active membranes
• P Systems with Elementary Active Membranes: Beyond NP and coNP
• Remarks on the computational power of some restricted variants of P systems with active membranes
• Membrane Computing

zbMATH Keywords

membrane computingsatisfiability problemP-completenessactive membranesdissolution rules

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On uniformity within \(NC^ 1\)
• A polynomial complexity class in P systems using membrane division
• P systems with active membranes: Attacking NP-complete problems
• Title not available (Why is that?)
• Seeking computational efficiency boundaries: the Păun's conjecture
• Title not available (Why is that?)
• The computational power of membrane systems under tight uniformity conditions
• Sublinear-space P systems with active membranes
• Uniformity is Weaker than Semi-Uniformity for Some Membrane Systems
• Membrane Computing
• A new method to simulate restricted variants of polarizationless P systems with active membranes
• Polarizationless P systems with active membranes: computational complexity aspects
• Solving a special case of the P conjecture using dependency graphs with dissolution
• A Turing machine simulation by P systems without charges
• Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems
• P systems attacking hard problems beyond NP: a survey
• Remarks on the computational power of some restricted variants of P systems with active membranes
• Membrane Dissolution and Division in P
• Simulating Turing machines with polarizationless P systems with active membranes
• A Characterisation of NL Using Membrane Systems without Charges and Dissolution
• Active Membrane Systems Without Charges and Using Only Symmetric Elementary Division Characterise P
• Title not available (Why is that?)

Cited In (2)

• Universal enzymatic numerical P systems with small number of enzymatic rules
• Unary resolution: characterizing \textsc{Ptime}

This page was built for publication: A characterisation of \textbf{P} by \textbf{DLOGTIME}-uniform families of polarizationless P systems using only dissolution rules

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