Fixed-dimensional energy games are in pseudo-polynomial time
From MaRDI portal
Publication:3449481
DOI10.1007/978-3-662-47666-6_21zbMATH Open1440.68122arXiv1502.06875OpenAlexW1622764697MaRDI QIDQ3449481FDOQ3449481
Sylvain Schmitz, Marcin Jurdziński, Ranko Lazić
Publication date: 4 November 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Abstract: We generalise the hyperplane separation technique (Chatterjee and Velner, 2013) from multi-dimensional mean-payoff to energy games, and achieve an algorithm for solving the latter whose running time is exponential only in the dimension, but not in the number of vertices of the game graph. This answers an open question whether energy games with arbitrary initial credit can be solved in pseudo-polynomial time for fixed dimensions 3 or larger (Chaloupka, 2013). It also improves the complexity of solving multi-dimensional energy games with given initial credit from non-elementary (Br'azdil, Janv{c}ar, and Kuv{c}era, 2010) to 2EXPTIME, thus establishing their 2EXPTIME-completeness.
Full work available at URL: https://arxiv.org/abs/1502.06875
Recommendations
- Polynomial-time algorithms for energy games with special weight structures
- Faster algorithms for mean-payoff games
- Generalized mean-payoff and energy games
- A faster deterministic exponential time algorithm for energy games and mean payoff games
- Polynomial-time algorithms for energy games with special weight structures
Cites Work
- The covering and boundedness problems for vector addition systems
- Generalized mean-payoff and energy games
- Energy Games in Multiweighted Automata
- Solving Parity Games on Integer Vectors
- Strategy synthesis for multi-dimensional quantitative objectives
- Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
- 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
- Alternating Vector Addition Systems with States
- Optimal Bounds for Multiweighted and Parametrised Energy Games
Cited In (21)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Synthesis for Multi-weighted Games with Branching-Time Winning Conditions
- On the complexity of resource-bounded logics
- Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
- Deciding Fast Termination for Probabilistic VASS with Nondeterminism
- Hyperplane separation technique for multidimensional mean-payoff games
- On decidability and complexity of low-dimensional robot games
- Bounding Average-Energy Games
- Title not available (Why is that?)
- The fixed initial credit problem for partial-observation energy games is \textsc{Ack}-complete
- Strategic reasoning with a bounded number of resources: the quest for tractability
- Reachability games with relaxed energy constraints
- Extending Finite-Memory Determinacy by Boolean Combination of Winning Conditions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Model checking and synthesis for branching multi-weighted logics
- Efficient Algorithms for Omega-Regular Energy Games
- State of the Art in Logics for Verification of Resource-Bounded Multi-Agent Systems
This page was built for publication: Fixed-dimensional energy games are in pseudo-polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449481)
