On decidability and complexity of low-dimensional robot games
DOI10.1016/J.JCSS.2019.08.003zbMATH Open1436.91002OpenAlexW2969299158WikidataQ127353368 ScholiaQ127353368MaRDI QIDQ2009641FDOQ2009641
Authors: 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
Recommendations
- The complexity of robot games on the integer line
- Undecidability of two-dimensional robot games
- On robot games of degree two
- Robot games with states in dimension one
- Robot motion planning: A game-theoretic foundation
- The frontier of decidability in partially observable recursive games
- Robust multidimensional mean-payoff games are undecidable
- scientific article; zbMATH DE number 7650410
- Simulation of action theories and an application to general game-playing robots
- The complexity of solving reachability games using value and strategy iteration
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05)
Cites Work
- Alternating-time temporal logic
- Title not available (Why is that?)
- Borel determinacy
- Small universal register machines
- Automata, logics, and infinite games. A guide to current research
- Title not available (Why is that?)
- Reachability in two-dimensional vector addition systems with states is PSPACE-complete
- Automated Technology for Verification and Analysis
- An automata-theoretic approach to branching-time model checking
- Pushdown processes: Games and model-checking
- Fixed-dimensional energy games are in pseudo-polynomial time
- Energy parity games
- Title not available (Why is that?)
- Energy games in multiweighted automata
- Solving parity games on integer vectors
- Integer vector addition systems with states
- Computer Science Logic
- Title not available (Why is that?)
- Reachability in succinct one-counter games
- One-counter stochastic games
- Affine extensions of integer vector addition systems with states
- Reachability games on extended vector addition systems with states
- Robot games with states in dimension one
- On robot games of degree two
- Undecidability of two-dimensional robot games
- The complexity of robot games on the integer line
- Hyperplane separation technique for multidimensional mean-payoff games
- On the complexity of counter reachability games
- Bounding Average-Energy Games
- The context-freeness problem is coNP-complete for flat counter systems
- Title not available (Why is that?)
- Minkowski games
- Z-reachability problem for games on 2-dimensional vector addition systems with states is in P
- Perfect half space games
- Monotonic and Downward Closed Games
Cited In (7)
- Integer weighted automata on infinite words
- Integer Weighted Automata on Infinite Words
- Optimizing reachability sets in temporal graphs by delaying
- Robot games with states in dimension one
- On robot games of degree two
- Undecidability of two-dimensional robot games
- The complexity of robot games on the integer line
This page was built for publication: On decidability and complexity of low-dimensional robot games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2009641)
