A substructural logic for layered graphs

作者：Collinson Matthew^*; McDonald Kevin; Pym David

来源：Journal of Logic and Computation, 2014, 24(4): 953-988.

DOI：10.1093/logcom/exu002

• Substructural logic
• semantics
• proof theory
• graphs
• layers
• complex systems
• modelling

Complex systems, be they natural or synthetic, are ubiquitous. In particular, complex networks of devices and services underpin most of society%26apos;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.

• 出版日期2014-8