Manzoni, L., Poças, D., & Porreca, A. E. (2014). Simple reaction systems and their classification. International Journal of Foundations of Computer Science, 25(04), 441-457.
Abstract
Reaction systems are a model of computation inspired by biochemical reactions involving reactants, inhibitors and products from a finite background set. 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 each reaction. We prove that “simple” reaction systems, having at most one reactant and one inhibitor per reaction, suffice in order to simulate arbitrary systems. Finally, we show that the equivalence relation of mutual simulation induces exactly five linearly ordered classes of reaction systems characterizing well-known subclasses of the functions over Boolean lattices, such as the constant, additive (join-semilattice endomorphisms), monotone, and antitone functions.
@article{manzoni2014simple,
title={Simple reaction systems and their classification},
author={Manzoni, Luca and Po{\c{c}}as, Diogo and Porreca, Antonio E},
journal={International Journal of Foundations of Computer Science},
volume={25},
number={04},
pages={441--457},
year={2014},
publisher={World Scientific}
}
Manzoni, L., Poças, D., & Porreca, A. E. (2014). Simple reaction systems and their classification. International Journal of Foundations of Computer Science, 25(04), 441-457.
Abstract Reaction systems are a model of computation inspired by biochemical reactions involving reactants, inhibitors and products from a finite background set. 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 each reaction. We prove that “simple” reaction systems, having at most one reactant and one inhibitor per reaction, suffice in order to simulate arbitrary systems. Finally, we show that the equivalence relation of mutual simulation induces exactly five linearly ordered classes of reaction systems characterizing well-known subclasses of the functions over Boolean lattices, such as the constant, additive (join-semilattice endomorphisms), monotone, and antitone functions.
Link to the online copy
Bibtex file
@article{manzoni2014simple, title={Simple reaction systems and their classification}, author={Manzoni, Luca and Po{\c{c}}as, Diogo and Porreca, Antonio E}, journal={International Journal of Foundations of Computer Science}, volume={25}, number={04}, pages={441--457}, year={2014}, publisher={World Scientific} }