Salomaa, A. (2013). Minimal and almost minimal reaction systems. Natural Computing, 12(3), 369-376.
Abstract
In reaction systems introduced by Ehrenfeucht and Rozenberg the number of resources is, by definition, at least 2. If it is exactly 2, the system is referred to as minimal. We compare minimal reaction systems with almost minimal ones, where the number of resources equals 3. The difference turns out to be huge. While many central problems for minimal systems are of low polynomial complexity, the same problems in the almost minimal case are NP- or co-NP-complete. The situation resembles the difference between 2-SAT and 3-SAT, also from the point of view of techniques used. We also compare maximal sequence lengths obtainable in the two cases. We are concerned only with the most simple variant of reaction systems.
Salomaa, A. (2013). Minimal and almost minimal reaction systems. Natural Computing, 12(3), 369-376.
Abstract In reaction systems introduced by Ehrenfeucht and Rozenberg the number of resources is, by definition, at least 2. If it is exactly 2, the system is referred to as minimal. We compare minimal reaction systems with almost minimal ones, where the number of resources equals 3. The difference turns out to be huge. While many central problems for minimal systems are of low polynomial complexity, the same problems in the almost minimal case are NP- or co-NP-complete. The situation resembles the difference between 2-SAT and 3-SAT, also from the point of view of techniques used. We also compare maximal sequence lengths obtainable in the two cases. We are concerned only with the most simple variant of reaction systems.
Link to the online copy
Bibtex file @article{salomaa2013minimal, title={Minimal and almost minimal reaction systems}, author={Salomaa, Arto}, journal={Natural Computing}, volume={12}, number={3}, pages={369--376}, year={2013}, publisher={Springer} }