Dennunzio, A., Formenti, E., Manzoni, L., & Porreca, A. E. (2015). Ancestors, descendants, and gardens of Eden in reaction systems. Theoretical Computer Science, 608, 16-26.
Abstract
This paper analyses several problems related to finding and counting ancestor and descendant states, as well as gardens of Eden (i.e., states without predecessors) in reaction systems. The focus is on the complexity of finding and counting preimages and ancestors that are minimal with respect to cardinality. It turns out that the problems concerning gardens of Eden seem to require the presence of an NP-oracle to be solved.
Bibtex file
@article{dennunzio2015ancestors,
title={Ancestors, descendants, and gardens of Eden in reaction systems},
author={Dennunzio, Alberto and Formenti, Enrico and Manzoni, Luca and Porreca, Antonio E},
journal={Theoretical Computer Science},
volume={608},
pages={16--26},
year={2015},
publisher={Elsevier}
}
Dennunzio, A., Formenti, E., Manzoni, L., & Porreca, A. E. (2015). Ancestors, descendants, and gardens of Eden in reaction systems. Theoretical Computer Science, 608, 16-26.
Abstract This paper analyses several problems related to finding and counting ancestor and descendant states, as well as gardens of Eden (i.e., states without predecessors) in reaction systems. The focus is on the complexity of finding and counting preimages and ancestors that are minimal with respect to cardinality. It turns out that the problems concerning gardens of Eden seem to require the presence of an NP-oracle to be solved.
Link to the online copy
Bibtex file @article{dennunzio2015ancestors, title={Ancestors, descendants, and gardens of Eden in reaction systems}, author={Dennunzio, Alberto and Formenti, Enrico and Manzoni, Luca and Porreca, Antonio E}, journal={Theoretical Computer Science}, volume={608}, pages={16--26}, year={2015}, publisher={Elsevier} }