On the complexity of modal separation logics

MaRDI QIDQ5224566zbMATH OpenFDO

Authors Stéphane Demri, Raul Fervari

Publication date 24 July 2019

zbMATH Keywords

complexityexpressive powermodel-checkingrelation-changing logicssatisfiabilityseparation logics

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Modal logic (including the logic of norms) (03B45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• The power of modal separation logics
• The effects of modalities in separation logics (extended abstract)
• Separation logics and modalities: a survey
• On the almighty wand
• Undecidability of propositional separation logic and its neighbours

Cited in

(24)

• The effect of bounding the number of primitive propositions and the depth of nesting on the complexity of modal logic
• Verification of dynamic bisimulation theorems in Coq
• On the complexity of graded modal logics with converse
• Axiomatising logics with separating conjunction and modalities
• On the relative complexity of labelled modal tableaux
• On the size of shortest modal descriptions
• Undecidability of propositional separation logic and its neighbours
• Internal proof calculi for modal logics with separating conjunction
• Inf-datalog, Modal Logic and Complexities
• Complexity Results for Modal Dependence Logic
• Separating Graph Logic from MSO
• scientific article; zbMATH DE number 1088193 (Why is no real title available?)
• scientific article; zbMATH DE number 6819808 (Why is no real title available?)
• The effects of modalities in separation logics (extended abstract)
• Decidability and complexity of fibred logics without shared connectives
• On temporal and separation logics
• Modal logics with composition on finite forests: expressivity and complexity
• The power of modal separation logics
• Copy and remove as dynamic operators
• The Complexity of Decomposing Modal and First-Order Theories
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• An auxiliary logic on trees: on the tower-hardness of logics featuring reachability and submodel reasoning
• An undecidability result for separation logic with theory reasoning
• Reasoning about sequences of memory states

This page was built for publication: On the complexity of modal separation logics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5224566)