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 ^[log] to (poly)
Preimage problems for reaction systems / Dennunzio, Alberto; Formenti, Enrico; Manzoni, Luca; Porreca Antonio, E.. - STAMPA. - 8977:(2015), pp. 537-548. ( 9th International Conference on Language and Automata Theory and Applications, LATA 2015 Nice, France 2015) [10.1007/978-3-319-15579-1_42].
Preimage problems for reaction systems
Manzoni Luca;
2015-01-01
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 ^[log] to (poly)File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
cover+index+capitolo.pdf
Accesso chiuso
Tipologia:
Documento in Versione Editoriale
Licenza:
Copyright Editore
Dimensione
290.53 kB
Formato
Adobe PDF
|
290.53 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
