Reaction systems are a model of computation inspired by biochemical reactions introduced by Ehrenfeucht and Rozenberg. Two problems related to the dynamics (the evolution of the state with respect to time) of reaction systems, namely, the occurrence and the convergence problems, were recently investigated by Salomaa. In this paper, we prove that both problems are PSPACE-complete when the numerical parameter of the problems (i.e. the time step when a specified element must appear) is given as input. Moreover, they remain PSPACE-complete even for minimal reaction systems.

On the complexity of occurrence and convergence problems in reaction systems

Manzoni Luca;
2015-01-01

Abstract

Reaction systems are a model of computation inspired by biochemical reactions introduced by Ehrenfeucht and Rozenberg. Two problems related to the dynamics (the evolution of the state with respect to time) of reaction systems, namely, the occurrence and the convergence problems, were recently investigated by Salomaa. In this paper, we prove that both problems are PSPACE-complete when the numerical parameter of the problems (i.e. the time step when a specified element must appear) is given as input. Moreover, they remain PSPACE-complete even for minimal reaction systems.
2015
Pubblicato
http://www.springerlink.com/content/1567-7818/
File in questo prodotto:
File Dimensione Formato  
Formenti2015_Article_OnTheComplexityOfOccurrenceAnd.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 552.96 kB
Formato Adobe PDF
552.96 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/2947772
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 17
social impact