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.

Reachability in resource-bounded reaction systems

Manzoni Luca;
2016-01-01

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.
File in questo prodotto:
File Dimensione Formato  
copertina, indice, contributo.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 282.26 kB
Formato Adobe PDF
282.26 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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/2947978
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 8
social impact