Published March 2, 2015
| Version v1
Conference paper
Preimage Problems for Reaction Systems
- Others:
- Dipartimento di Informatica Sistemistica e Comunicazione (DISCo) ; Università degli Studi di Milano-Bicocca = University of Milano-Bicocca (UNIMIB)
- 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)
- Adrian-Horia Dediu
- Enrico Formenti
- Carlos Martín-Vide
- Bianca Truthe
- ANR-09-BLAN-0164,EMC,Emergence dans les modèles de calcul(2009)
Description
We investigate the computational complexity of some problems related to preimages and ancestors of states of reaction systems. In particular, we prove that finding a minimum-cardinality preimage or ancestor, computing their size, or counting them are all intractable problems, with complexity ranging from FP^{NP[logn]} to FPSPACE(poly).
Abstract
International audience
Additional details
- URL
- https://hal.science/hal-01313640
- URN
- urn:oai:HAL:hal-01313640v1
- Origin repository
- UNICA