Reaction systems are a recent formal model inspired by the chemical reactions that happen inside cells and possess many different dynamical behaviours. In this work we continue a recent investigation of the complexity of detecting some interesting dynamical behaviours in reaction system. We prove that detecting global behaviours such as the presence of global attractors is PSPACE-complete. Deciding the presence of cycles in the dynamics and many other related problems are also PSPACE-complete. Deciding bijectivity is, on the other hand, a coNP-complete problem.

Formenti, E., Manzoni, L., Porreca, A. (2014). Cycles and global attractors of reaction systems. In Descriptional Complexity of Formal Systems, 16th International Workshop, DCFS 2014 (pp.114-125). Springer [10.1007/978-3-319-09704-6_11].

Cycles and global attractors of reaction systems

MANZONI, LUCA;PORRECA, ANTONIO ENRICO
2014

Abstract

Reaction systems are a recent formal model inspired by the chemical reactions that happen inside cells and possess many different dynamical behaviours. In this work we continue a recent investigation of the complexity of detecting some interesting dynamical behaviours in reaction system. We prove that detecting global behaviours such as the presence of global attractors is PSPACE-complete. Deciding the presence of cycles in the dynamics and many other related problems are also PSPACE-complete. Deciding bijectivity is, on the other hand, a coNP-complete problem.
slide + paper
reaction systems; computational complexity; natural computing
English
16th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2014
2014
Jürgensen, H; Karhumäki, J; Okhotin, A
Descriptional Complexity of Formal Systems, 16th International Workshop, DCFS 2014
9783319097039
2014
8614
114
125
reserved
Formenti, E., Manzoni, L., Porreca, A. (2014). Cycles and global attractors of reaction systems. In Descriptional Complexity of Formal Systems, 16th International Workshop, DCFS 2014 (pp.114-125). Springer [10.1007/978-3-319-09704-6_11].
File in questo prodotto:
File Dimensione Formato  
Paper.pdf

Solo gestori archivio

Dimensione 302.87 kB
Formato Adobe PDF
302.87 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/60280
Citazioni
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 19
Social impact