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

DOI10.1007/S10601-016-9243-0zbMath1390.90102OpenAlexW2169859441MaRDI QIDQ1706770

Carlo Comin, Romeo Rizzi, Roberto Posenato

Publication date: 28 March 2018

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-016-9243-0

zbMATH Keywords

workflowshypergraphsmean payoff gamestemporal consistencypseudo-polynomial time algorithmssimple temporal networksdisjunctive temporal problems

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Deterministic network models in operations research (90B10)

Related Items (6)

Dynamic controllability via timed game automata ⋮ Instantaneous reaction-time in dynamic consistency checking of conditional simple temporal networks ⋮ Solving mean-payoff games via quasi dominions ⋮ Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier

Uses Software

• PGSolver
• GitHub
• HyTN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Faster algorithms for mean-payoff games
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Positional strategies for mean payoff games
• Temporal constraint networks
• The complexity of mean payoff games on graphs
• From local to global consistency in temporal constraint networks
• Backtracking algorithms for disjunctions of temporal constraints
• Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games
• CTP: A new constraint-based formalism for conditional, temporal planning
• USING STRATEGY IMPROVEMENT TO STAY ALIVE
• On a routing problem
• Symmetric Strategy Improvement
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Recoverability of Communication Protocols--Implications of a Theoretical Study
• Handling contingency in temporal constraint networks: from consistency to controllabilities
• Temporal representation and reasoning in artificial intelligence: A review

This page was built for publication: Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games