Docherty, Simon Robert; (2019) Bunched logics: a uniform approach. Doctoral thesis (Ph.D), UCL (University College London).

Preview

Text Simon Docherty - Bunched Logics - A Uniform Approach.pdf Download (1MB) | Preview

Abstract

Bunched logics have found themselves to be key tools in modern computer science, in particular through the industrial-level program verification formalism Separation Logic. Despite this—and in contrast to adjacent families of logics like modal and substructural logic—there is a lack of uniform methodology in their study, leaving many evident variants uninvestigated and many open problems unresolved. In this thesis we investigate the family of bunched logics—including previously unexplored intuitionistic variants—through two uniform frameworks. The first is a system of duality theorems that relate the algebraic and Kripke-style interpretations of the logics; the second, a modular framework of tableaux calculi that are sound and complete for both the core logics themselves, as well as many classes of bunched logic model important for applications in program verification and systems modelling. In doing so we are able to resolve a number of open problems in the literature, including soundness and completeness theorems for intuitionistic variants of bunched logics, classes of Separation Logic models and layered graph models; decidability of layered graph logics; a characterisation theorem for the classes of bunched logic model definable by bunched logic formulae; and the failure of Craig interpolation for principal bunched logics. We also extend our duality theorems to the categorical structures suitable for interpreting predicate versions of the logics, in particular hyperdoctrinal structures used frequently in Separation Logic.

Download activity - last month

Export as CSVXMLJSON

Download activity - last 12 months

Export as CSVJSONXML

Downloads by country - last 12 months

Export as JSONXMLCSV

Archive Staff Only

View Item