Name
Abstract | ||
|---|---|---|
Membrane computing, which is a computational model based on cell activity, has considerable attention as one of new paradigms of computations. In the general membrane computing, computationally hard problems have been solved in a polynomial number of steps using an exponential number of membranes. However, reduction of the number of membranes must be considered to make P system more realistic model. In the paper, we propose an asynchronous P system using branch and bound, which is a well known optimization technique, to reduce the number of membranes. The proposed P system solves the satisfiability problem (SAT) with n variables and m clauses, and works in O(m2
<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup>
) sequential steps or O(mn) parallel steps. The number of membranes used in the proposed P system is evaluated using a computational simulation. The experimental result shows the effectiveness of the proposed P system. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/CANDAR.2017.71 | 2017 Fifth International Symposium on Computing and Networking (CANDAR) |
Keywords | Field | DocType |
membrane computing,satisfiability problem,branch and bound | Asynchronous communication,Branch and bound,Exponential function,Polynomial,Computer science,Boolean satisfiability problem,Algorithm,Membrane,Membrane computing,P system | Conference |
ISSN | ISBN | Citations |
2379-1888 | 978-1-5386-2088-5 | 0 |
PageRank | References | Authors |
0.34 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuki Jimen | 1 | 0 | 0.34 |
| Akihiro Fujiwara | 2 | 122 | 27.25 |