We propose two kinds of asynchronous SN P systems for sorting. We first propose an anynchronous SN P system that works as a comparator, which sorts two binary numbers of m bits. The SN P systems work in O(m) sequential steps or O(logm) parallel steps using O(m) neurons. We next propose an asynchronous SN P system that simulates a sorting network, which sorts n binary numbers of m bits using the above comparator. The SN P system works in O (mn log n) sequential steps or O (log m log n) parallel steps using O(mn log n) neurons. Finally, we propose another SN P system that sorts n binary numbers of m bits. The SN P system is based on a round robin tournament, and works in O(mn~2) sequential steps or O(log m) parallel steps using O(mn~2) neurons.
展开▼
机译：我们提出了两种异步SN P系统进行分类。我们首先提出了一个与比较器一起使用的任何SN P系统，其分类了两个二进制数的M位。 SN P系统使用O（m）神经元的O（m）顺序步骤或o（logm）并行步骤。我们接下来提出了一种异步SN P系统，用于使用上述比较器对分类网络进行排序的分类网络。 SN P系统使用O（MN Log N）神经元在O（MN Log N）顺序步骤或O（log m log n）并行步骤中。最后，我们提出了另一个SN P系统，这些系统排序了n个二进制数的M位。 SN P系统基于循环锦标赛，并使用O（Mn〜2）神经元的O（Mn〜2）顺序步骤或O（log m）并行步骤。
展开▼
