2025/07/09 by Dazhu Li, Li, Dazhu, Sujata Ghosh +3 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2508.00004
openalex publication_date 2025/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The game of Cops and Robbers is an important model for studying computational queries in pursuit-evasion environments, among others. As recent logical explorations have shown, its structure exhibits appealing analogies with modal logic. In this paper, we enrich the game with a setting in which players may have imperfect information. We propose a new formal framework, Epistemic Logic of Cops and Robbers (ELCR), to make the core notions of the game precise, for instance, players' positions, observational power and inference. Applying ELCR to analyze the game, we obtain an automated way to track interactions between players and characterize their information updates during the game. The update mechanism is defined by a novel dynamic operator, and we compare it with some relevant paradigms from the game and logic perspectives. We study various properties of ELCR including axiomatization and decidability. To our knowledge, this is the first attempt to explore these games from a formal point of view where (partial) information available to players is taken into account.