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 FPNP[log n] to FPSPACE(poly).

Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A. (2015). Preimage problems for reaction systems. In 9th International Conference on Language and Automata Theory and Applications, LATA 2015; Nice; France; 2-6 March 2015 (pp.537-548). Springer Verlag [10.1007/978-3-319-15579-1_42].

Preimage problems for reaction systems

DENNUNZIO, ALBERTO
Primo
;
MANZONI, LUCA
Penultimo
;
PORRECA, ANTONIO ENRICO
Ultimo
2015

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, with complexity ranging from FPNP[log n] to FPSPACE(poly).
slide + paper
Computational complexity; Reaction systems; Computer Science (all); Theoretical Computer Science
English
9th International Conference on Language and Automata Theory and Applications, LATA 2015
2015
9th International Conference on Language and Automata Theory and Applications, LATA 2015; Nice; France; 2-6 March 2015
9783319155784
2015
8977
537
548
http://springerlink.com/content/0302-9743/copyright/2005/
none
Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A. (2015). Preimage problems for reaction systems. In 9th International Conference on Language and Automata Theory and Applications, LATA 2015; Nice; France; 2-6 March 2015 (pp.537-548). Springer Verlag [10.1007/978-3-319-15579-1_42].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/107098
Citazioni
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
Social impact