On the complexity of occurrence and convergence problems in reaction systems

Creators: Formenti, Enrico; Manzoni, Luca; Porreca, Antonio

Others:: Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC) ; Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA); Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S) ; Université Nice Sophia Antipolis (1965 - 2019) (UNS) ; COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA); Dipartimento di Informatica Sistemistica e Comunicazione (DISCo) ; Università degli Studi di Milano-Bicocca = University of Milano-Bicocca (UNIMIB)

Description

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.

Abstract

International audience

On the complexity of occurrence and convergence problems in reaction systems

Description

Abstract

Additional details