Intuitionistic Layered Graph Logic: Semantics and Proof Theory
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2018-10-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/3163/pdf |
| _version_ | 1797268547603267584 |
|---|---|
| author | Simon Docherty David Pym |
| author_facet | Simon Docherty David Pym |
| author_sort | Simon Docherty |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:34:13Z |
| format | Article |
| id | doaj.art-2977ce04760a4df282b2d49aa0c34021 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:34:13Z |
| publishDate | 2018-10-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-2977ce04760a4df282b2d49aa0c340212024-03-08T10:27:52ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742018-10-01Volume 14, Issue 410.23638/LMCS-14(4:11)20183163Intuitionistic Layered Graph Logic: Semantics and Proof TheorySimon DochertyDavid PymModels 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.https://lmcs.episciences.org/3163/pdfcomputer science - logic in computer sciencef.4.1 |
| spellingShingle | Simon Docherty David Pym Intuitionistic Layered Graph Logic: Semantics and Proof Theory Logical Methods in Computer Science computer science - logic in computer science f.4.1 |
| title | Intuitionistic Layered Graph Logic: Semantics and Proof Theory |
| title_full | Intuitionistic Layered Graph Logic: Semantics and Proof Theory |
| title_fullStr | Intuitionistic Layered Graph Logic: Semantics and Proof Theory |
| title_full_unstemmed | Intuitionistic Layered Graph Logic: Semantics and Proof Theory |
| title_short | Intuitionistic Layered Graph Logic: Semantics and Proof Theory |
| title_sort | intuitionistic layered graph logic semantics and proof theory |
| topic | computer science - logic in computer science f.4.1 |
| url | https://lmcs.episciences.org/3163/pdf |
| work_keys_str_mv | AT simondocherty intuitionisticlayeredgraphlogicsemanticsandprooftheory AT davidpym intuitionisticlayeredgraphlogicsemanticsandprooftheory |