Bialgebraic semantics for logic programming

DOI10.2168/LMCS-11(1:14)2015MaRDI QIDQ5246719zbMATH OpenOpenAlexFDO

Authors Filippo Bonchi, Fabio Zanasi

Publication date 22 April 2015

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.06095

zbMATH Keywords

bialgebrascoalgebrae on presheavescompositionalitylogic programming

Mathematics Subject Classification ID

Categorical semantics of formal languages (18C50) Logic programming (68N17) Semantics in the theory of computing (68Q55) Abstract data types; algebraic specification (68Q65)

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.

Recommendations

• Bialgebraic methods in structural operational semantics (invited talk)
• Saturated semantics for coalgebraic logic programming
• Bialgebraic methods and modal logic in structural operational semantics
• Coalgebraic semantics for parallel derivation strategies in logic programming
• Bialgebraic semantics and recursion (extended abstract)

Cited in

(20)

• Bialgebraic methods and modal logic in structural operational semantics
• Bi-inductive structural semantics
• Syntactical investigations into \(BI\) logic and \(BB^ \prime I\) logic
• Logic programming: laxness and saturation
• Iterated covariant powerset is not a monad
• Saturated semantics for coalgebraic logic programming
• scientific article; zbMATH DE number 4129055 (Why is no real title available?)
• Classical BI: Its Semantics and Proof Theory
• Universal constructions for (co)relations: categories, monoidal categories, and props
• scientific article; zbMATH DE number 1931660 (Why is no real title available?)
• scientific article; zbMATH DE number 786486 (Why is no real title available?)
• Bialgebraic semantics and recursion (extended abstract)
• scientific article; zbMATH DE number 1441841 (Why is no real title available?)
• Coalgebraic semantics for probabilistic logic programming
• scientific article; zbMATH DE number 2242590 (Why is no real title available?)
• Lawvere categories as composed PROPs
• Category theoretic semantics for theorem proving in logic programming: embracing the laxness
• scientific article; zbMATH DE number 7649893 (Why is no real title available?)
• Reductive logic, proof-search, and coalgebra: a perspective from resource semantics
• Weakening and iterating laws using string diagrams

Describes a project that uses

Uses Software

• CoALP

This page was built for publication: Bialgebraic semantics for logic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5246719)