Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time

DOI10.1007/978-3-662-47666-6_21zbMath1440.68122arXiv1502.06875OpenAlexW1622764697MaRDI QIDQ3449481

Sylvain Schmitz, Marcin Jurdziński, Ranko Lazić

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of game theory (91A80)

Related Items (20)

Hyperplane separation technique for multidimensional mean-payoff games ⋮ State of the Art in Logics for Verification of Resource-Bounded Multi-Agent Systems ⋮ The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete ⋮ Unnamed Item ⋮ Reachability games with relaxed energy constraints ⋮ Synthesis for Multi-weighted Games with Branching-Time Winning Conditions ⋮ Model checking and synthesis for branching multi-weighted logics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounding Average-Energy Games ⋮ Unnamed Item ⋮ Deciding Fast Termination for Probabilistic VASS with Nondeterminism ⋮ Simple stochastic games with almost-sure energy-parity objectives are in NP and conp ⋮ Strategic reasoning with a bounded number of resources: the quest for tractability ⋮ On decidability and complexity of low-dimensional robot games ⋮ Unnamed Item ⋮ On the complexity of resource-bounded logics ⋮ Unnamed Item ⋮ Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions

Cites Work

• The covering and boundedness problems for vector addition systems
• Strategy synthesis for multi-dimensional quantitative objectives
• Solving Parity Games on Integer Vectors
• Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
• Optimal Bounds for Multiweighted and Parametrised Energy Games
• Generalized Mean-payoff and Energy Games
• Alternating Vector Addition Systems with States
• Energy Games in Multiweighted Automata
• Reachability Games on Extended Vector Addition Systems with States
• Infinite-state energy games
• Z-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P

This page was built for publication: Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time