On Composing Finite Forests with Modal Logics

Publikation: Beitrag in FachzeitschriftForschungsartikelBeigetragenBegutachtung

Beitragende

  • Bartosz Bednarczyk - , Professur für Computational Logic, University of Wrocław (Autor:in)
  • Stéphane Demri - (Autor:in)
  • Raul Fervari - (Autor:in)
  • Alessio Mansutti - (Autor:in)

Abstract

We study the expressivity and complexity of two modal logics interpreted on finite forests and equipped with standard modalities to reason on submodels. The logic extends the modal logic K with the composition operator from ambient logic whereas features the separating conjunction from separation logic. Both operators are second-order in nature. We show that is as expressive as the graded modal logic (on trees) whereas is strictly less expressive than . Moreover, we establish that the satisfiability problem is Tower-complete for , whereas it is (only) AExpPol-complete for , a result that is surprising given their relative expressivity. As by-products, we solve open problems related to sister logics such as static ambient logic and modal separation logic.

Details

OriginalspracheEnglisch
Aufsatznummer3569954
Seitenumfang46
FachzeitschriftACM transactions on computational logic
Jahrgang24
Ausgabenummer2
PublikationsstatusVeröffentlicht - 3 Apr. 2023
Peer-Review-StatusJa

Externe IDs

Scopus 85152943708

Schlagworte