Asynchronous P Systems for a Compare-and-Exchange Operation and Sorting
Asynchronous P Systems for a Compare-and-Exchange Operation and Sorting
复制标题
用于比较和交换操作和排序的异步 P 系统
DOI：
10.1109/candar.2015.21
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Fujiwara
中科院分区：
文献类型：
--
作者：
Yutaka Nishida;A. Fujiwara
在本文中，我们考虑异步P系统，这是一种基于细胞活动的计算模型，并提出了两个执行比较交换操作和排序的P系统。我们首先提出了一个异步P系统，用于两个m位二进制数的比较和交换操作。P系统通过使用O(m)种对象、固定数量的膜和尺寸为O(m)的演化规则，以O(m)个步骤工作。接下来，我们利用上述异步P系统作为子系统，提出了一个对m位的n个二进制数进行排序的异步P系统。P系统通过使用O（mn）类型的物体、固定数量的膜和尺寸为O（mn）的演化规则，以O（mn2）步骤工作。
In the present paper, we consider asynchronous P systems, which is a computational model based on cell activity, and propose two P systems that execute a compare-and-exchange operation and sorting. We first propose an asynchronous P system for the compare-and-exchange operation of two binary numbers of m bits. The P system works in O(m) steps by using O(m) types of objects, a constant number of membranes and evolution rules of size O(m). We next propose an asynchronous P system for sorting of n binary numbers of m bits by using the above asynchronous P system as a sub-system. The P system works in O(mn2) steps by using O(mn) types of objects, a constant number of membranes, and evolution rules of size O(mn).