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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Modal Logic for the Hide and Seek Game

  • Qian Chen,
  • Dazhu Li,
  • Yaxin Tu,
  • Sujata Ghosh,
  • Fenrong Liu

摘要

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.