On decidability and complexity of low-dimensional robot games
From MaRDI portal
Publication:2009641
DOI10.1016/j.jcss.2019.08.003zbMath1436.91002OpenAlexW2969299158WikidataQ127353368 ScholiaQ127353368MaRDI QIDQ2009641
J. Reichert, Reino Niskanen, Igor Potapov
Publication date: 29 November 2019
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://ora.ox.ac.uk/objects/uuid:a63d3805-648d-41da-b21b-88d4dbd304d3
Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (3)
Integer weighted automata on infinite words ⋮ Optimizing reachability sets in temporal graphs by delaying ⋮ Integer Weighted Automata on Infinite Words
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Borel determinacy
- Small universal register machines
- Reachability in succinct one-counter games
- Robot games with states in dimension one
- Energy parity games
- Pushdown processes: Games and model-checking
- Automata, logics, and infinite games. A guide to current research
- Hyperplane separation technique for multidimensional mean-payoff games
- On Robot Games of Degree Two
- Solving Parity Games on Integer Vectors
- One-Counter Stochastic Games
- On The Complexity of Counter Reachability Games*
- Bounding Average-Energy Games
- Energy Games in Multiweighted Automata
- Integer Vector Addition Systems with States
- Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time
- Alternating-time temporal logic
- The Context-Freeness Problem Is coNP-Complete for Flat Counter Systems
- Reachability Games on Extended Vector Addition Systems with States
- Undecidability of Two-dimensional Robot Games
- Reachability in Two-Dimensional Vector Addition Systems with States Is PSPACE-Complete
- Minkowski Games
- Z-reachability Problem for Games on 2-dimensional Vector Addition Systems with States is in P
- Computer Science Logic
- An automata-theoretic approach to branching-time model checking
- Monotonic and Downward Closed Games
- Automated Technology for Verification and Analysis
This page was built for publication: On decidability and complexity of low-dimensional robot games
