Arithmetic Operations and Factorization using Asynchronous P Systems

Abstract

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(m³) sequential steps using O(m²) 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(4^m  × m² log m) sequential steps using O(m²) types of objects.