Reaction systems, a formalism describing biochemical reactions in terms of sets of reactants, inhibitors, and products, are known to have a PSPACE-complete configuration reachability problem. We show that the complexity of the problem remains unchanged even for some classes of resource-bounded reaction systems, where we disallow either inhibitors or reactants. We also prove that the complexity decreases to NP in the specific case of inhibitorless reaction systems using only one reactant per reaction.

Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A. (2016). Reachability in resource-bounded reaction systems. In Language and Automata Theory and Applications (pp.592-602). Springer Verlag [10.1007/978-3-319-30000-9_45].

Reachability in resource-bounded reaction systems

DENNUNZIO, ALBERTO
Primo
;
MANZONI, LUCA
Penultimo
;
PORRECA, ANTONIO ENRICO
2016

Abstract

Reaction systems, a formalism describing biochemical reactions in terms of sets of reactants, inhibitors, and products, are known to have a PSPACE-complete configuration reachability problem. We show that the complexity of the problem remains unchanged even for some classes of resource-bounded reaction systems, where we disallow either inhibitors or reactants. We also prove that the complexity decreases to NP in the specific case of inhibitorless reaction systems using only one reactant per reaction.
slide + paper
Discrete dynamical systems; Natural computing; Reachability; Reaction systems; Unconventional models of computation; Computer Science (all); Theoretical Computer Science
English
International Conference on Language and Automata Theory and Applications (LATA) March 14-18
2016
Language and Automata Theory and Applications
9783319299990
2016
9618
592
602
http://springerlink.com/content/0302-9743/copyright/2005/
open
Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A. (2016). Reachability in resource-bounded reaction systems. In Language and Automata Theory and Applications (pp.592-602). Springer Verlag [10.1007/978-3-319-30000-9_45].
File in questo prodotto:
File Dimensione Formato  
Paper.pdf

accesso aperto

Descrizione: Preprint
Dimensione 390.25 kB
Formato Adobe PDF
390.25 kB Adobe PDF Visualizza/Apri

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/107073
Citazioni
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 8
Social impact