NDLI: Hyper temporal networks : A tractable generalization of simple temporal networks and its relation to mean payoff games

Please wait, while we are loading the content...

Hyper temporal networks : A tractable generalization of simple temporal networks and its relation to mean payoff games

Content Provider	Springer Nature Link
Author	Comin, Carlo Posenato, Roberto Rizzi, Romeo
Copyright Year	2016
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.
Starting Page	152
Ending Page	190
Page Count	39
File Format	PDF
ISSN	13837133
Journal	Constraints
Volume Number	22
Issue Number	2
e-ISSN	15729354
Language	English
Publisher	Springer US
Publisher Date	2016-03-23
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Simple temporal networks Temporal consistency Hypergraphs Pseudo-polynomial time algorithms Mean payoff games Disjunctive temporal problems Workflows Artificial Intelligence (incl. Robotics) Optimization Computing Methodologies Operation Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Artificial Intelligence Computational Theory and Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Checking dynamic consistency of conditional hyper temporal networks via mean payoff games

Periodic Constraint Satisfaction Problems: Tractable Subclasses

ℚ-bounds consistency for the spread constraint with variable mean

New Tractable Classes From Old

A hybrid tractable class for non-binary CSPs

Tractability in constraint satisfaction problems: a survey

Tractable classes for CSPs of arbitrary arity: from theory to practice

Checking Dynamic Consistency of Conditional Hyper Temporal Networks via Mean Payoff Games (Hardness and (pseudo) Singly-Exponential Time Algorithm)

Towards statistical consistency for stochastic constraint programming

Hyper temporal networks : A tractable generalization of simple temporal networks and its relation to mean payoff games

Similar Documents

Checking dynamic consistency of conditional hyper temporal networks via mean payoff games

Periodic Constraint Satisfaction Problems: Tractable Subclasses

ℚ-bounds consistency for the spread constraint with variable mean

New Tractable Classes From Old

A hybrid tractable class for non-binary CSPs

Tractability in constraint satisfaction problems: a survey

Tractable classes for CSPs of arbitrary arity: from theory to practice

Checking Dynamic Consistency of Conditional Hyper Temporal Networks via Mean Payoff Games (Hardness and (pseudo) Singly-Exponential Time Algorithm)

Towards statistical consistency for stochastic constraint programming

Hyper temporal networks : A tractable generalization of simple temporal networks and its relation to mean payoff games