Insertion Sort with Self-reproducing Comparator P System

Abstract

We present in this paper a self-reproducing comparator P~system that simulates insertion sort. The comparator ${\Pi }_c$ is a degree-2 membrane and structured as $\mu ={[}_{h_0}{[}_{h_1}{]}_{h_1}{[}_{h_2}{]}_{h_2}{]}_{h_0}$. A maximizing ${\Pi }_c$ compares two multisets $a$ and $b$ where $\min (|a|,|b|)$ is stored in compartment $h_1$ while $\max (|a|,|b|)$ is stored in compartment $h_2$. A conditional reproduction rule triggers ${\Pi }_c$ to clone itself out via compartment division followed by endocytosis of the cloned compartment. We present the process of sorting as a collection of transactions implemented in hierarchical levels where each level has different concurrent or serialized steps.

5 pages, 1 figure, submitted as contributed article to 15th National Conference on Information Technology Education, Leyte Normal University, Tacloban City, Leyte, Philippines, 19-21 October 2017