Name
Abstract | ||
|---|---|---|
In the present paper, we consider fully asynchronous parallelism in membrane computing, and propose two asynchronous P systems for the satisfiability (SAT) and Hamiltonian cycle problem. We first propose an asynchronous P system that solves SAT with n variables and tit clauses, and show that the proposed P system computes SAT in O(mn2(n)) sequential steps or O(mn) parallel steps using O(mn) kinds of objects. We next propose an asynchronous P system that solves the Hamiltonian cycle problem with n nodes, and show that the proposed P system computes the problem in O(n!) sequential steps or O(n(2)) parallel steps using O(n(2)) kinds of objects. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1587/transinf.E95.D.746 | IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS |
Keywords | Field | DocType |
membrane computing, asynchronous parallelism, SAT, Hamiltonian cycle problem | Asynchronous communication,Discrete mathematics,Pattern recognition,Computer science,Satisfiability,Theoretical computer science,Hamiltonian path problem,Artificial intelligence,Membrane computing,P system | Journal |
Volume | Issue | ISSN |
E95D | 3 | 1745-1361 |
Citations | PageRank | References |
11 | 0.70 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hirofumi Tagawa | 1 | 11 | 1.38 |
| Akihiro Fujiwara | 2 | 122 | 27.25 |