Parameterized complexity and approximability of coverability problems in weighted Petri netsReport as inadecuate




Parameterized complexity and approximability of coverability problems in weighted Petri nets - Download this document for free, or read online. Document in PDF available to download.

1 SAMOVAR - Services répartis, Architectures, MOdélisation, Validation, Administration des Réseaux 2 ENSIIE - Ecole Nationale Supérieure d-Informatique pour l-Industrie et l-Entreprise 3 LRI - Laboratoire de Recherche en Informatique 4 CentraleSupélec 5 PRISM - Parallélisme, Réseaux, Systèmes, Modélisation

Abstract : Many databases have been filled with the chemical reactions found in scientific publications and the information associated with efficiency , chemical products involved



They can be used to define functions representing costs such as the ecoligical impact of the reactions. A major challenge is to use computer driven optimization in order to improve synthesis process. The objective is to provide algorithms to help determining a pathway series of reactions for the synthesis of a molecule. Usually, a chemist proposes a pathway adapted from an existing one. Our goal is to determine optimum pathways from the reactions recorded in the database. As, the classical Petri nets do not allows us to consider the optimization component, a weighted model has to be defined and the complexity of the associated problems studied. In this paper we introduce the weighted Petri nets in which each transition is associated with a weight. We define the Minimum Weight Synthesis Problem: find a minimum weight series of transitions to fire to produce a given target component. It mainly differ from classical coverability as it is an optimization problem. We prove that this problem is decidable but EXPSPACE-hard and that there is no polynomial approximation even when both in and outdegree are fixed to two and the target state is a single component. We also consider a more constraint version of the problem limiting the number of fired transitions. We prove this problem falls into PSPACE and the parametrized versions into XP but it remains not approximable.

Keywords : Petri net coverability problem Minimum weight synthesis problem Parameterized complexity Approximability





Author: Dimitri Watel - Marc-Antoine Weisser - Dominique Barth -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents