Modal Logics for the Poison Game: Axiomatization and Undecidability

Penghao Du, Fenrong Liu, and Dazhu Li [PDF]

Abstract

In the tradition of memory logic, two comparatively weak systems, poison modal logic (PML) and poison sabotage logic (PSL), were studied in existing literature to capture the so-called poison game, which originally served as a paradigm to reason about graph-theoretical notions and was recently shown to have important applications in the theory of abstract argumentation. In this work, we continue to explore the technical aspect of the two logics and complete the existing results by providing our solutions to the questions identified in the literature (Grossi and Rey, 2019a; 2019b; Blando et al., 2020). Precisely, we show that (i) neither of them can be embedded in fixed-variable fragment of first-order logic, on the basis of the existing findings for PML and PSL, (ii) PSL has an undecidable satisfiability problem, and (iii) motivated by the existing axiomatization results for the standard memory logic (Areces et al., 2012), we axiomatize the two logics in a broader setting with enrichments from hybrid logic. As we shall see, in line with the fact that PSL is strictly weaker than PML, the calculus for the hybrid PSL developed will also be a ‘fragment’ of that for the hybrid PML.

Keywords

Memory logic, Hybrid logic, Graph game logic, Credulously admissible set, Axiomatization, Undecidability

References

1. C. Areces, R. Fervari, G. Hoffmann, and M. Martel. (2018) Undecidability of relation-changing modal logics. In A. Madeira and M. Benevides, editors, Proceedings of DaLĺ 2017, volume 10669 of LNCS, 1–16. Springer.
2. C. Areces, D. Figueira, S. Figueira, and S. Mera. (2008) Expressive power and decidability for memory logics. In W. Hodges and R. de Queiroz, editors, WoLLIC 2008, volume 5110 of LNCS, 56–58. Springer.
3. C. Areces, D. Figueira, S. Figueira, and S. Mera. (2011) The expressive power of memory logics. The Review of Symbolic Logic, 4:290–318.
4. C. Areces, D. Figueira, D. Gorín, and S. Mera. (2009) Tableaux and model checking for memory logics. In M. Giese and A. Waaler, editors, Automated Reasoning with Analytic Tableaux and Related Methods, volume 5607 of LNAI, 47–61. Springer.
5. C. Areces, S. Figueira, and S. Mera. (2012) Completeness results for memory logics. Annals of Pure and Applied Logic, 163:961–972.
6. G. Aucher, J. van Benthem, and D. Grossi. (2015) Sabotage modal logic: Some model and proof theoretic aspects. In W. van der Hoek, W. Holliday, and W. Wang, editors, Proceedings of LORI 2015, volume 9394 of LNCS, 1–13. Springer.
7. G. Aucher, J. van Benthem, and D. Grossi. (2018) Modal logics of sabotage revisited. Journal of Logic and Computation, 28(2):269–303.
8. A. Baltag, D. Li, and M. Y. Pedersen. (2019) On the right path: A modal logic for supervised learning. In P. Blackburn, E. Lorini, and M. Guo, editors, Proceedings of LORI 2019, volume 11813 of LNCS, 1–14. Springer.
9. A. Baltag, D. Li, and M. Y. Pedersen. (2022) A modal logic for supervised learning. Journal of Logic, Language and Information, 31:213–234.
10. R. Berger. (1966) The Undecidability of the Domino Problem. AMS.
11. P. Blackburn, M. de Rijke, and Y. Venema. (2001) Modal Logic. Cambridge University Press.
12. P. Blackburn and J. Seligman. (1995) Hybrid languages. Journal of Logic, Language and Information, 4:251–272.
13. F. Z. Blando, K. Mierzewski, and C. Areces. (2020) The modal logics of the poison game. In F. Liu, H. Ono, and J. Yu, editors, Knowledge, Proof and Dynamics. The Fourth Asian Workshop on Philosophical Logic, 3–23. Springer.
14. T. Bolander and P. Blackburn. (2007) Termination for hybrid tableaus. Journal of Logic and Computation, 17:517–554.
15. Q. Chen and D. Li. (2024) Logic of the hide and seek game: characterization, axiomatization, decidability. In N. Gierasimczuk and F. R. Velázquez-Quesada, editors, Proceedings of DaLĺ 2023, volume 14401 of LNCS, 20–34. Springer, 2024.
16. P. Du and Q. Chen. (2024) Axiomatization of hybrid logic of link variations. In N. Gierasimczuk and F. R. Velázquez-Quesada, editors, Proceedings of DaLĺ 2023, volume 14401 of LNCS, 35–51. Springer.
17. P. Duchet and H. Meyniel. (1993) Kernels in directed graph: a poison game. Discrete Mathematics, 115:273–276.
18. N. Gierasimczuk, L. Kurzen, and F. R. Velázquez-Quesada. (2009) Learning and teaching as a game: a sabotage approach. In X. He, J. Horty, and E. Pacuit, editors, Proceedings of LORI 2009, volume 5834 of LNCS, 119–132. Springer.
19. D. Grossi and S. Rey. (2019a) Credulous acceptability, poison games and modal logic. In N. Agmon, M. E. Taylor, E. Elkind, and M. Veloso, editors, Proceedings of AAMAS 2019, 1994–1996.
20. D. Grossi and S. Rey. (2019b) Credulous acceptability, poison games and modal logic. http://arxiv.org/abs/1901.09180v2
21. A. Indrzejczak and M. Zawidzki. (2013) Decision procedures for some strong hybrid logics. Logic and Logical Philosophy, 22:389–409.
22. D. Li. (2020) Losing connection: the modal logic of definable link deletion. Journal of Logic and Computation, 30:715–743.
23. D. Li, S. Ghosh, and F. Liu. (2025) Reasoning under uncertainty in the game of Cops and Robbers. Synthese, https://doi.org/10.1007/s11229-025-05165-6
24. D. Li, S. Ghosh, F. Liu, and Y. Tu. (2021) On the subtle nature of a simple logic of the hide and seek game. In A. Silva, R. Wassermann, and R. de Queiroz, editors, Proceedings of WoLLIC 2021, volume 13038 of LNCS, 201–218. Springer.
25. D. Li, S. Ghosh, F. Liu, and Y. Tu. (2023) A simple logic of the hide and seek game. Studia Logica, 111:821–853.
26. K. Sano, F. Liu, and D. Li. (2024) Hybrid logic of the hide and seek game. Studia Logica, https://doi.org/10.1007/s11225-024-10149-7
27. B. ten Cate. (2005) Model Theory for Extended Modal Languages. PhD thesis, Institute for Logic, Language and Computation, University of Amsterdam, Amsterdam.
28. D. Thompson. (2020) Local fact change logic. In F. Liu, H. Ono, and J. Yu, editors, Knowledge, Proof and Dynamics, Logic in Asia: Studia Logica Library, 73–96. Springer.
29. J. van Benthem. (2005) An essay on sabotage and obstruction. In D. Hutter and W. Stephan, editors, Mechanizing Mathematical Reasoning, volume 2605 of LNCS, 268–276. Springer.
30. J. van Benthem. (2011) Logical Dynamics of Information and Interaction. Cambridge University Press.
31. J. van Benthem, L. Li, C. Shi, and H. Yin. (2023) Hybrid sabotage modal logic. Journal of Logic and Computation, 33(6):1216–1242.
32. J. van Benthem and F. Liu. (2020) Graph games and logic design. In F. Liu, H. Ono, and J. Yu, editors, Knowledge, Proof and Dynamics, 125–146. Springer.
33. J. van Benthem and F. Liu, editors. (2025) Graph Games and Logic Design: Recent Developments and Future Directions (To Appear). Springer.
34. J. van Benthem, K. Mierzewski, and F. Z. Blando. (2022) The modal logic of stepwise removal. The Review of Symbolic Logic, 15(1):36–63.
35. H. van Ditmarsch, W. van der Hoek, and B. Kooi. (2007) Dynamic Epistemic Logic, volume 337 of Synthese Library. Springer, 2007.
36. M. Vardi. (1995) On the complexity of bounded–variable queries. In Proceedings of the ACM 14th Symposium on Principles of Database Systems, 266–276.
37. A. Varzi. (2019) Mereology. In E. N. Zalta, editor, The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Spring 2019 edition.