Docherty, S;
Pym, D;
(2018)
Intuitionistic Layered Graph Logic: Semantics and Proof Theory.
Logical Methods in Computer Science (LMCS)
, 14
(4)
, Article 11. 10.23638/LMCS-14(4:11)2018.
Preview |
Text
Pym_1702.05795.pdf - Published Version Download (981kB) | Preview |
Abstract
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.
| Type: | Article |
|---|---|
| Title: | Intuitionistic Layered Graph Logic: Semantics and Proof Theory |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.23638/LMCS-14(4:11)2018 |
| Publisher version: | http://doi.org/0.23638/LMCS-14(4:11)2018 |
| Language: | English |
| Additional information: | Copyright © The Author 2018. This article is distributed under the terms of the Creative Commons Attribution 4.0 License (http://www.creativecommons.org/licenses/by/4.0/) which permits any use, reproduction and distribution of the work without further permission provided the original work is attributed |
| Keywords: | Complex systems, modelling, graphs, layered graphs, substructural logic, bunched logic, layered graph logic, predicate logic, tableaux, Kripke semantics, algebraic semantics, decidability, finite model property, Stone-type duality, soundness and completeness, bigraphs, pointer logic, hyperdoctrine. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10059609 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
