Dennunzio, A., Formenti, E., Manzoni, L., & Porreca, A. E. (2016, March). Reachability in resource-bounded reaction systems. In International Conference on Language and Automata Theory and Applications (pp. 592-602). Springer, Cham.
Abstract
Reaction systems, a formalism describing biochemical reactions in terms of sets of reactants, inhibitors, and products, are known to have a PSPACE-complete configuration reachability problem. We show that the complexity of the problem remains unchanged even for some classes of resource-bounded reaction systems, where we disallow either inhibitors or reactants. We also prove that the complexity decreases to NP in the specific case of inhibitorless reaction systems using only one reactant per reaction.
Bibtex file
@inproceedings{dennunzio2016reachability,
title={Reachability in resource-bounded reaction systems},
author={Dennunzio, Alberto and Formenti, Enrico and Manzoni, Luca and Porreca, Antonio E},
booktitle={International Conference on Language and Automata Theory and Applications},
pages={592--602},
year={2016},
organization={Springer}
}
Dennunzio, A., Formenti, E., Manzoni, L., & Porreca, A. E. (2016, March). Reachability in resource-bounded reaction systems. In International Conference on Language and Automata Theory and Applications (pp. 592-602). Springer, Cham.
Abstract Reaction systems, a formalism describing biochemical reactions in terms of sets of reactants, inhibitors, and products, are known to have a PSPACE-complete configuration reachability problem. We show that the complexity of the problem remains unchanged even for some classes of resource-bounded reaction systems, where we disallow either inhibitors or reactants. We also prove that the complexity decreases to NP in the specific case of inhibitorless reaction systems using only one reactant per reaction.
Link to the online copy
Bibtex file @inproceedings{dennunzio2016reachability, title={Reachability in resource-bounded reaction systems}, author={Dennunzio, Alberto and Formenti, Enrico and Manzoni, Luca and Porreca, Antonio E}, booktitle={International Conference on Language and Automata Theory and Applications}, pages={592--602}, year={2016}, organization={Springer} }