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

Simple Temporal Networks (STNs) are used in many applications, as they provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables.We introduce Hyper Temporal Networks (TNs), a strict generalization of STNs, to overcome the limitation of considering only conjunctions of constraints.In a Hyper Temporal Network a single temporal 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.As in STNs, a TN is consistent when a real value can be assigned to each temporal variable satisfying all the constraints.We show the computational complexity for this generalization and propose effective reduction algorithms for checking consistency of TNs unveiling the link with the field of Mean Payoff Games.TNs are meant as a light generalization of STNs offering an interesting compromise.On one side, as we show, there exist practical pseudo-polynomial time algorithms for checking consistency and computing feasible schedules for TNs.On the other side, TNs allow to express natural constraints that cannot be expressed by STNs like "trigger off an event exactly delta min after the occurrence of the last event in a set''.