Simon Docherty ; David Pym - Intuitionistic Layered Graph Logic: Semantics and Proof Theory

lmcs:3163 - Logical Methods in Computer Science, October 31, 2018, Volume 14, Issue 4 - https://doi.org/10.23638/LMCS-14(4:11)2018
Intuitionistic Layered Graph Logic: Semantics and Proof TheoryArticle

Authors: Simon Docherty ; David Pym

    Models of complex systems are widely used in the physical and social sciences, and the concept of layering, typically building upon graph-theoretic structure, is a common feature. We describe an intuitionistic substructural logic called ILGL that gives an account of layering. The logic is a bunched system, combining the usual intuitionistic connectives, together with a non-commutative, non-associative conjunction (used to capture layering) and its associated implications. We give soundness and completeness theorems for a labelled tableaux system with respect to a Kripke semantics on graphs. We then give an equivalent relational semantics, itself proven equivalent to an algebraic semantics via a representation theorem. We utilise this result in two ways. First, we prove decidability of the logic by showing the finite embeddability property holds for the algebraic semantics. Second, we prove a Stone-type duality theorem for the logic. By introducing the notions of ILGL hyperdoctrine and indexed layered frame we are able to extend this result to a predicate version of the logic and prove soundness and completeness theorems for an extension of the layered graph semantics . We indicate the utility of predicate ILGL with a resource-labelled bigraph model.


    Volume: Volume 14, Issue 4
    Published on: October 31, 2018
    Accepted on: August 9, 2018
    Submitted on: February 28, 2017
    Keywords: Computer Science - Logic in Computer Science,F.4.1

    Consultation statistics

    This page has been seen 1264 times.
    This article's PDF has been downloaded 542 times.