UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

A substructural logic for layered graphs

Collinson, M; McDonald, K; Pym, D; (2014) A substructural logic for layered graphs. Journal of Logic and Computation 10.1093/logcom/exu002. Green open access

[img] PDF
collinson-mcdonald-pym-layers.pdf

Download (1MB)

Abstract

Complex systems, be they natural or synthetic, are ubiquitous. In particular, complex networks of devices and services underpin most of society's operations. By their very nature, such systems are difficult to conceptualize and reason about effectively. The concept of layering is widespread in complex systems, but has not been considered conceptually. Noting that graphs are a key formalism in the description of complex systems, we establish a notion of a layered graph. We provide a logical characterization of this notion of layering using a non-associative, non-commutative substructural, separating logic. We provide soundness and completeness results for a class of algebraic models that includes layered graphs, which give a mathematically substantial semantics to this very weak logic. We explain, via examples, applications in information processing and security.

Type: Article
Title: A substructural logic for layered graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1093/logcom/exu002
Publisher version: http://dx.doi.org/ 10.1093/logcom/exu002
Language: English
Additional information: This is a pre-copyedited, author-produced PDF of an article accepted for publication in Journal of Logic and Computation following peer review. The definitive publisher-authenticated version Collinson, M; McDonald, K; Pym, D; (2014) A substructural logic for layered graphs. Journal of Logic and Computation. is available online at: http://dx.doi.org/10.1093/logcom/exu002
UCL classification: UCL
UCL > Provost and Vice Provost Offices
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/1425723
Downloads since deposit
74Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item