The power of modal separation logics. (19th December 2019)

• Record Type: Journal Article
• Authors: Demri, Stéphane; Fervari, Raul
• Is Part Of: Journal of logic and computation. Volume 29:Number 8(2019)
• Page Start: 1139
• Page End: 1184
• Publication Date: 2019-12-19
• Subjects: Separation logics -- relation-changing logics -- satisfiability -- model-checking -- complexity -- expressive power; Logic programming -- Periodicals; Logic, Symbolic and mathematical -- Periodicals; Computational complexity -- Periodicals; 005.115
• DOI: 10.1093/logcom/exz019
• Languages: English
• ISSNs: 0955-792X

Abstract

Abstract: We introduce a modal separation logic MSL whose models are memory states from separation logic and the logical connectives include modal operators as well as separating conjunction and implication from separation logic. With such a combination of operators, some fragments of MSL can be seen as genuine modal logics whereas some others capture standard separation logics, leading to an original language to speak about memory states. We analyse the decidability status and the computational complexity of several fragments of MSL, obtaining surprising results by design of proof methods that take into account the modal and separation features of MSL. For example, the satisfiability problem for the fragment of MSL with $\Diamond $, the difference modality $\langle \neq \rangle $ and separating conjunction $\ast $ is shown Tower -complete whereas the restriction either to $\Diamond $ and $\ast $ or to $\langle \neq \rangle $ and $\ast $ is only NP-complete. We establish that the full logic MSL admits an undecidable satisfiability problem. Furthermore, we investigate variants of MSL with alternative semantics and we build bridges with interval temporal logics and with logics equipped with sabotage operators.