Solving 3-SAT in distributed P systems with string objects

DOI10.1016/J.TCS.2023.113976MaRDI QIDQ6162062zbMATH OpenOpenAlexFDO

Authors Kelvin C. Buño, Henry N. Adorna

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.113976

zbMATH Keywords

distributed P-systemsmembrane computingSAT

Mathematics Subject Classification ID

Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07) Grammars and rewriting systems (68Q42) Computational aspects of satisfiability (68R07)

Recommendations

• Distributed computation of a \(k\) P systems with active membranes for SAT using clause completion
• A new approach for solving SAT by P systems with active membranes
• P Systems with Proteins on Membranes and Membrane Division
• Solving SAT by P Systems with Active Membranes in Linear Time in the Number of Variables
• scientific article; zbMATH DE number 1958491

Cites work

• A computational complexity theory in membrane computing
• A new approach for solving SAT by P systems with active membranes
• A survey of results on evolution-communication P systems with energy
• A uniform solution to SAT using membrane creation
• An efficient time-free solution to SAT problem by P systems with proteins on membranes
• Computing with membranes
• Distributed computation of a \(k\) P systems with active membranes for SAT using clause completion
• scientific article; zbMATH DE number 1583885 (Why is no real title available?)
• scientific article; zbMATH DE number 5671765 (Why is no real title available?)
• Membrane systems with promoters/inhibitors
• P Systems with String Objects and with Communication by Request
• Solution to PSPACE-complete problem using P systems with active membranes with time-freeness
• Solving HPP and SAT by P systems with active membranes and separation rules
• Solving SAT by P Systems with Active Membranes in Linear Time in the Number of Variables
• Time-free solution to SAT problem using P systems with active membranes
• Tissue-like P systems with evolutional symport/antiport rules
• Uniform solutions to SAT and subset sum by spiking neural P systems

Cited in

(5)

• A polynomial-time reduction from the 3SAT problem to the generalized string puzzle problem
• Distributed computation of a \(k\) P systems with active membranes for SAT using clause completion
• On maximal parallel application of rules in rewriting P systems
• Solving the SAT problem with the string multiset rewriting calculus
• Solving SAT by restricted spiking neural P systems with temporal division rules

This page was built for publication: Solving 3-SAT in distributed P systems with string objects

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