On decidability and complexity of low-dimensional robot games

DOI10.1016/J.JCSS.2019.08.003MaRDI QIDQ2009641zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

decidabilitywinning strategyreachability gamesvector addition gameinteger vector addition system

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05)

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

Cites work

• scientific article; zbMATH DE number 1670482 (Why is no real title available?)
• scientific article; zbMATH DE number 1361127 (Why is no real title available?)
• scientific article; zbMATH DE number 6862142 (Why is no real title available?)
• scientific article; zbMATH DE number 6790161 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• Affine extensions of integer vector addition systems with states
• Alternating-time temporal logic
• An automata-theoretic approach to branching-time model checking
• Automata, logics, and infinite games. A guide to current research
• Automated Technology for Verification and Analysis
• Borel determinacy
• Bounding Average-Energy Games
• Computer Science Logic
• Energy games in multiweighted automata
• Energy parity games
• Fixed-dimensional energy games are in pseudo-polynomial time
• Hyperplane separation technique for multidimensional mean-payoff games
• Integer vector addition systems with states
• Minkowski games
• Monotonic and Downward Closed Games
• On robot games of degree two
• On the complexity of counter reachability games
• One-counter stochastic games
• Perfect half space games
• Pushdown processes: Games and model-checking
• Reachability games on extended vector addition systems with states
• Reachability in succinct one-counter games
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Robot games with states in dimension one
• Small universal register machines
• Solving parity games on integer vectors
• The complexity of robot games on the integer line
• The context-freeness problem is coNP-complete for flat counter systems
• Undecidability of two-dimensional robot games
• Z-reachability problem for games on 2-dimensional vector addition systems with states is in P

Cited in

(7)

• The complexity of robot games on the integer line
• 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

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)