Hyper Temporal Networks: A Tractable Generalization of Simple Temporal Networks and its relation to Mean Payoff Games

Abstract : Simple Temporal Networks (STNs) provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables. In this paper we introduce Hyper Temporal Networks (HyTNs), a strict generalization of STNs, to overcome the limitation of considering only conjunctions of constraints but maintaining a practical efficiency in the consistency check of the instances. In a Hyper Temporal Network a single temporal hyperarc constraint may be defined as a set of two or more maximum delay constraints which is satisfied when at least one of these delay constraints is satisfied. HyTNs are meant as a light generalization of STNs offering an interesting compromise. On one side, there exist practical pseudo-polynomial time algorithms for checking consistency and computing feasible schedules for HyTNs. On the other side, HyTNs offer a more powerful model accommodating natural constraints that cannot be expressed by STNs like “Trigger off exactly δ min before (after) the occurrence of the first (last) event in a set.”, which are used to represent synchronization events in some process aware information systems/workflow models proposed in the literature.
Type de document :
Article dans une revue
Constraints, Springer Verlag, 2017, 22 (2), pp.152-190. 〈10.1007/s10601-016-9243-0〉
Liste complète des métadonnées

Littérature citée [44 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01577455
Contributeur : Admin Upem <>
Soumis le : vendredi 25 août 2017 - 17:29:10
Dernière modification le : jeudi 5 juillet 2018 - 14:45:41

Fichier

stnmaxmpg3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Carlo Comin, Roberto Posenato, Romeo Rizzi. Hyper Temporal Networks: A Tractable Generalization of Simple Temporal Networks and its relation to Mean Payoff Games. Constraints, Springer Verlag, 2017, 22 (2), pp.152-190. 〈10.1007/s10601-016-9243-0〉. 〈hal-01577455〉

Partager

Métriques

Consultations de la notice

273

Téléchargements de fichiers

44