scientific article; zbMATH DE number 7350776

zbMath1499.68200arXiv1709.08991MaRDI QIDQ4989405

Martin Gairing, Matthias Mnich, Rahul Savani, John Fearnley

Publication date: 25 May 2021

Full work available at URL: https://arxiv.org/abs/1709.08991

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

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 (2)

The stochastic arrival problem ⋮ Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets

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
• Unique end of potential line
• 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
• Deterministic Random Walks on the Two-Dimensional Grid
• The Simple Reachability Problem in Switch Graphs
• SWITCHING GRAPHS
• The Complexity of Markov Decision Processes
• Alternation
• Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
• Reachability Switching Games

This page was built for publication: