Reaction Systems Made Simple A Normal Form and a Classification Theorem

摘要

Reaction systems are models of computation inspired by the interactions between biochemical reactions. We define a notion of multi-step simulation among reaction systems and derive a classification with respect to the amount of resources (reactants and inhibitors) involved in the reactions. We prove that one reactant and one inhibitor per reaction are sufficient to simulate arbitrary systems. Finally, we show that the equivalence relation of mutual simulation induces exactly five linearly ordered classes of reaction systems.