On decidability and complexity of low-dimensional robot games
DOI10.1016/J.JCSS.2019.08.003zbMATH Open1436.91002OpenAlexW2969299158WikidataQ127353368 ScholiaQ127353368MaRDI QIDQ2009641FDOQ2009641
Reino Niskanen, J. Reichert, 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Monotonic and Downward Closed Games
Cited In (4)
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)
