Dennunzio, A., Formenti, E., Manzoni, L., & Porreca, A. E. (2015, March). Preimage problems for reaction systems. In International Conference on Language and Automata Theory and Applications (pp. 537-548). Springer, Cham.
Abstract
We investigate the computational complexity of some problems related to preimages and ancestors of states of reaction systems. In particular, we prove that finding a minimum-cardinality preimage or ancestor, computing their size, or counting them are all intractable problems.
Bibtex file
@inproceedings{dennunzio2015preimage,
title={Preimage problems for 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={537--548},
year={2015},
organization={Springer}
}
Dennunzio, A., Formenti, E., Manzoni, L., & Porreca, A. E. (2015, March). Preimage problems for reaction systems. In International Conference on Language and Automata Theory and Applications (pp. 537-548). Springer, Cham.
Abstract We investigate the computational complexity of some problems related to preimages and ancestors of states of reaction systems. In particular, we prove that finding a minimum-cardinality preimage or ancestor, computing their size, or counting them are all intractable problems.
Link to the online copy
Bibtex file @inproceedings{dennunzio2015preimage, title={Preimage problems for 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={537--548}, year={2015}, organization={Springer} }