Arithmetic Operations and Factorization using Asynchronous P Systems

In the present paper, we consider the asynchronous parallelism in membrane computing, and propose asynchronous P systems that perform two basic arithmetic operations and factorization. Since there is no restrictive assumption for application of rules, sequential and maximal parallel executions are allowed on the asynchronous P system. We first propose a P system that computes addition of two binary numbers of m bits. The P system works in O(m) sequential and parallel steps using O(m) types of objects. We next propose a P system for multiplication of the two binary numbers of m bits, and show that the P system works in O(m log m) parallel steps or O(m3) sequential steps using O(m2) types of objects. Finally, we propose a P system for factorization of a positive integer of $m$ bits using the above P system as a sub-system. The P system computes the factorization in O(m log m) parallel steps or O(4m × m2 log m) sequential steps using O(m2) types of objects.