Hyper temporal networks
详细信息 查看全文
- 作者：Carlo Comin ; Roberto Posenato ; Romeo Rizzi
- 关键词：Simple temporal networks ; Temporal consistency ; Hypergraphs ; Pseudo ; polynomial time algorithms ; Mean payoff games ; Disjunctive temporal problems ; Workflows
- 刊名：Constraints
- 出版年：2017
- 出版时间：April 2017
- 年：2017
- 卷：22
- 期：2
- 页码：152-190
- 全文大小：
- 刊物类别：Computer Science
- 刊物主题：Artificial Intelligence (incl. Robotics); Optimization; Computing Methodologies; Operation Research/Decision Theory;
- 出版者：Springer US
- ISSN：1572-9354
- 卷排序：22
文摘
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.