Insights into Modal Slash Logic and Modal Decidability

Tero Tulenheimo (1)

1 STL - Savoirs, Textes, Langage (STL) - UMR 8163

The present paper has a two-fold task. On the one hand, it aims to provide an overview on Independence friendly modal logic as defined in (Tulenheimo, 2003; Tulenheimo, 2004) and studied in a number of subsequent publications. For systematic reasons to be explained, the logic is here referred to as modal slash logic (MsL). On the other hand, we take a close look at a syntactic fragment of MsL, to be termed MsL_0, first formulated in (Tulenheimo and Sevenster, 2006). We push the study of this logic deeper at several points: a model-theoretic criterion is presented which serves to tell when a formula of MsL_0 is not truth-equivalent to any formula of basic modal logic (ML); the game-theoretic property of 'bounded quasi-positionality' of MsL_0 is studied in detail; an alternative syntax for MsL_0 is discerned and the logic obtained is shown to enjoy the property of quasi-locality (generalizing the notion of locality familiar from ML); and we formulate an asymmetric bisimulation concept and use it to prove that MsL_0 is not closed under complementation. Drawing from insights provided by the study of MsL_0, we conclude by general observations about claims made on the 'reasons' why various modal logics are computationally well-behaved.

Mots clés: complementation; decidability; expressivity; IF logic; independence; modal logic; slash logic

Domaines: Philosophie; Logique [math.LO]

Tero Tulenheimo. Insights into Modal Slash Logic and Modal Decidability. 2012, pp.1-63. ⟨halshs-00715648⟩