Bialgebraic Semantics for Logic Programming

Abstract

Bialgebrae provide an abstract framework encompassing the semantics of different kinds of computational models. In this paper we propose a bialgebraic approach to the semantics of logic programming. Our methodology is to study logic programs as reactive systems and exploit abstract techniques developed in that setting. First we use saturation to model the operational semantics of logic programs as coalgebrae on presheaves. Then, we make explicit the underlying algebraic structure by using bialgebrae on presheaves. The resulting semantics turns out to be compositional with respect to conjunction and term substitution. Also, it encodes a parallel model of computation, whose soundness is guaranteed by a built-in notion of synchronisation between different threads.

References in corpus (1)

• Connector algebras for C/E and P/T nets' interactions

Cited by in corpus (11)

• Interacting Hopf Algebras: the theory of linear systems
• Distances between States and between Predicates
• Expressive Logics for Coinductive Predicates
• An Introduction to Fuzzy & Annotated Semantic Web Languages
• Universal Constructions for (Co)Relations: categories, monoidal categories, and props
• Extending set functors to generalised metric spaces
• A Metalanguage for Guarded Iteration
• Coalgebraic Semantics for Probabilistic Logic Programming
• On Generalized Metric Spaces for the Simply Typed Lambda-Calculus (Extended Version)
• Weakening and Iterating Laws using String Diagrams
• Combining nondeterminism, probability, and termination: equational and metric reasoning