A complete axiomisation for quantifier-free separation logic
We present the first complete axiomatisation for quantifier-free separation logic. The logic is equipped with the standard concrete heaplet semantics and the proof system has no external feature such as nominals/labels. It is not possible to rely completely on proof systems for Boolean BI as the con...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Logical Methods in Computer Science
2021
|
| _version_ | 1826268453234802688 |
|---|---|
| author | Demri, S Lozes, E Mansutti, A |
| author_facet | Demri, S Lozes, E Mansutti, A |
| author_sort | Demri, S |
| collection | OXFORD |
| description | We present the first complete axiomatisation for quantifier-free separation logic. The logic is equipped with the standard concrete heaplet semantics and the proof system has no external feature such as nominals/labels. It is not possible to rely completely on proof systems for Boolean BI as the concrete semantics needs to be taken into account. Therefore, we present the first internal Hilbert-style axiomatisation for quantifier-free separation logic. The calculus is divided in three parts: the axiomatisation of core formulae where Boolean combinations of core formulae capture the expressivity of the whole logic, axioms and inference rules to simulate a bottom-up elimination of separating connectives, and finally structural axioms and inference rules from propositional calculus and Boolean BI with the magic wand. |
| first_indexed | 2024-03-06T21:09:53Z |
| format | Journal article |
| id | oxford-uuid:3dc7c9cb-05a7-4452-adbf-832e8f9cf745 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T21:09:53Z |
| publishDate | 2021 |
| publisher | Logical Methods in Computer Science |
| record_format | dspace |
| spelling | oxford-uuid:3dc7c9cb-05a7-4452-adbf-832e8f9cf7452022-03-26T14:21:31ZA complete axiomisation for quantifier-free separation logicJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:3dc7c9cb-05a7-4452-adbf-832e8f9cf745EnglishSymplectic ElementsLogical Methods in Computer Science2021Demri, SLozes, EMansutti, AWe present the first complete axiomatisation for quantifier-free separation logic. The logic is equipped with the standard concrete heaplet semantics and the proof system has no external feature such as nominals/labels. It is not possible to rely completely on proof systems for Boolean BI as the concrete semantics needs to be taken into account. Therefore, we present the first internal Hilbert-style axiomatisation for quantifier-free separation logic. The calculus is divided in three parts: the axiomatisation of core formulae where Boolean combinations of core formulae capture the expressivity of the whole logic, axioms and inference rules to simulate a bottom-up elimination of separating connectives, and finally structural axioms and inference rules from propositional calculus and Boolean BI with the magic wand. |
| spellingShingle | Demri, S Lozes, E Mansutti, A A complete axiomisation for quantifier-free separation logic |
| title | A complete axiomisation for quantifier-free separation logic |
| title_full | A complete axiomisation for quantifier-free separation logic |
| title_fullStr | A complete axiomisation for quantifier-free separation logic |
| title_full_unstemmed | A complete axiomisation for quantifier-free separation logic |
| title_short | A complete axiomisation for quantifier-free separation logic |
| title_sort | complete axiomisation for quantifier free separation logic |
| work_keys_str_mv | AT demris acompleteaxiomisationforquantifierfreeseparationlogic AT lozese acompleteaxiomisationforquantifierfreeseparationlogic AT mansuttia acompleteaxiomisationforquantifierfreeseparationlogic AT demris completeaxiomisationforquantifierfreeseparationlogic AT lozese completeaxiomisationforquantifierfreeseparationlogic AT mansuttia completeaxiomisationforquantifierfreeseparationlogic |