A Modal Logic for the Hide and Seek Game
摘要
We study the game of hide and seek in the form of a graph game from a modal logic perspective. A logic is proposed to express moves and strategies in the game, and we show how the addition of an equality constant that models the winning condition of the game makes the logic undecidable. There are certain decidable fragments of first-order logic which behave in a similar fashion with respect to this kind of language extension, and we add a new modal instance to that class. We discuss the relative expressive power of the proposed logic in comparison to the standard modal counterparts and provide a characterization theorem for its expressiveness. We show that the model checking problem for the resulting logic is \(\textsf{P}\) -complete. We also study an axiomatization of the logic, and explore the connection with related product logics, which helps us gain more insight towards the subtleties of the proposed framework. Although the logic is designed for the game with two players, a hider and a seeker, our results can easily be transferred to the settings with more players, and this kind of logical exploration enhances our understanding of the game itself.