Reachability Switching Games

DOI10.4230/LIPIcs.ICALP.2018.124zbMath1499.68201OpenAlexW2963086563MaRDI QIDQ5002810

Rahul Savani, John Fearnley, Martin Gairing, Matthias Mnich

Publication date: 28 July 2021

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9128/pdf/LIPIcs-ICALP-2018-124.pdf

zbMATH Keywords

reachabilityswitching systemsmodel checkingsimple stochastic gamedeterministic random walks

Mathematics Subject Classification ID

Applications of game theory (91A80) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Other nonclassical models of computation (68Q09)

Related Items (3)

Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets ⋮ Unnamed Item ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds

Uses Software

• PRISM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Did the train reach its destination: the complexity of finding a witness
• An algorithmic study of switch graphs
• A simplified NP-complete satisfiability problem
• The complexity of stochastic games
• Deterministic random walks on the integers
• Deterministic random walks on regular trees
• Rotor Walks and Markov Chains
• Quasirandom Load Balancing
• Simulating a Random Walk with Constant Error
• Chip-Firing and Rotor-Routing on Directed Graphs
• Deterministic Random Walks on the Two-Dimensional Grid
• The Simple Reachability Problem in Switch Graphs
• SWITCHING GRAPHS
• ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP
• ARRIVAL: Next Stop in CLS

This page was built for publication: Reachability Switching Games