Advertisement
Published in:
2015 | OriginalPaper | Chapter
Preimage Problems for Reaction Systems
Authors : Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Antonio E. Porreca
Published in: Language and Automata Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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, with complexity ranging from
$$\mathbf{FP}^{\mathbf{NP}[\log n]}$$
to
$$\mathbf{FPSPACE}(\mathrm{poly})$$
.