Modal Logics for the Poison Game: Axiomatization and Undecidability

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.