Checking dynamic consistency of conditional hyper temporal networks via mean payoff games. Hardness and (pseudo) singly-exponential time algorithm

DOI10.1016/j.ic.2017.08.008zbMath1390.68590arXiv1602.06260OpenAlexW2287181202MaRDI QIDQ1706164

Romeo Rizzi, Carlo Comin

Publication date: 21 March 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.06260

zbMATH Keywords

dynamic consistencyreaction timemean payoff gamesconditional temporal networkshyper-temporal networkssimple temporal networkssingly-exponential time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial-time algorithms for energy games with special weight structures
• Faster algorithms for mean-payoff games
• Efficient solution techniques for disjunctive temporal reasoning problems
• Positional strategies for mean payoff games
• Temporal constraint networks
• The complexity of mean payoff games on graphs
• CTP: A new constraint-based formalism for conditional, temporal planning
• Automata, logics, and infinite games. A guide to current research
• USING STRATEGY IMPROVEMENT TO STAY ALIVE
• On a routing problem
• The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average
• Temporal representation and reasoning in artificial intelligence: A review

This page was built for publication: Checking dynamic consistency of conditional hyper temporal networks via mean payoff games. Hardness and (pseudo) singly-exponential time algorithm