Symbolic domains and reachability for nets with trajectories - INRIA - Institut National de Recherche en Informatique et en Automatique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Symbolic domains and reachability for nets with trajectories

Résumé

This paper addresses the problem of reachability for timed models handling additional quantities progressing linearly such as distance of moving objects to a target. We first introduce a variant of Petri nets called trajectory nets where some places are standard control places containing tokens, and other places contain a simplified representation of trajectories of objects instead of tokens. We give a semantics for this model, and propose an abstraction of sets of equivalent configurations into symbolic domains. We show how to compute in polynomial time a symbolic representation of successors of configurations appearing in a domain, and prove that domains are closed under calculus of successors. Further, the set of domains for a fixed trajectory net is finite. When the control part of the model is bounded, reachability, coverability and safety properties involving distances can be checked in PSPACE on a sound, complete, and finite abstraction called a state class graph.
Fichier principal
Vignette du fichier
main.pdf (663.6 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-04330097 , version 1 (07-12-2023)

Licence

Paternité

Identifiants

  • HAL Id : hal-04330097 , version 1

Citer

Loïc Hélouët, Prerak Contractor. Symbolic domains and reachability for nets with trajectories. 2023. ⟨hal-04330097⟩
35 Consultations
27 Téléchargements

Partager

Gmail Facebook X LinkedIn More