Reaction Systems for Logical Operations and Sorting

In the present paper, we consider the reaction system, which is a computational model based on biochemical reactions in living cells, and propose reaction systems for logical operations and sorting. We first propose a reaction system that executes a two-input logical operations, such as AND, OR, and XOR, and show that the reaction system works in O (1) steps. We next propose a reaction system for a compare-and-swap operation of two binary numbers of m bits. We show that the reaction system works in O (m) parallel steps using O (m) types of objects and reaction rules. We finally propose a reaction system for sorting of n binary numbers of m bits. The reaction system is based on an idea of the odd-even sort, and we show that the reaction system works in O (mn) parallel steps using O (mn) types of objects and reaction rules.