Equivalence Criteria for Compositional IF Modal Logics

Tero Tulenheimo , Manuel Rebuschi (1)

1 LHSP - Laboratoire d'Histoire des Sciences et de Philosophie - Archives Henri Poincaré

An IF modal logic L with a compositional semantics is formulated, generalizing the logic LSD introduced in [19]. Syntactic fragments L1, L2, L3, L4 are discerned. For each fragment, we study the relation of Li-equivalence: an equivalence relation between pointed models holding if and only if they satisfy precisely the same formulas of Li. A criterion for Li-equivalence is formulated in terms of model-comparison games, by imposing further conditions in addition to bisimilarity. Using the resulting methods for establishing indistinguishability w.r.t. Li, the relative expressive powers of the four fragments are determined.

Mots clés: bisimulation; convergence; expressive power; independence friendly logic; transition system

Domaines: Philosophie; Logique en informatique [cs.LO]

Tero Tulenheimo, Manuel Rebuschi. Equivalence Criteria for Compositional IF Modal Logics. Electronic Notes in Theoretical Computer Science, 2009, 231, pp.153-173. ⟨10.1016/j.entcs.2009.02.034⟩. ⟨halshs-00556238⟩