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

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.

Download activity - last month

Export as XMLJSONCSV

Download activity - last 12 months

Export as JSONCSVXML

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item