Name
Abstract | ||
|---|---|---|
We consider the sabotage game as presented by van Benthem. In this game one player moves along the edges of a finite multigraph and the other player takes out a link after each step. One can consider usual algorithmic tasks like reachability, Hamilton path, or complete search as winning conditions for this game. As the game definitely ends after at most the number of edges steps, it is easy to see that solving the sabotage game for the mentioned tasks takes at most PSPACE in the size of the graph. In this paper we establish the PSPACE-hardness of this problem. Furthermore, we introduce a modal logic over changing models to express tasks corresponding to the sabotage games and we show that model checking this logic is PSPACE-complete. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1007/978-3-540-45138-9_47 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
model checking,modal logic | Combinatorial game theory,Strategy,Computer science,Theoretical computer science,Repeated game,Normal-form game,Sequential game,Game tree,Non-cooperative game,Extensive-form game,Distributed computing | Conference |
Volume | ISSN | Citations |
2747 | 0302-9743 | 19 |
PageRank | References | Authors |
1.34 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christof Löding | 1 | 326 | 28.57 |
| Philipp Rohde | 2 | 44 | 4.73 |