Coalgebraic semantics for derivations in logic programming

Ekaterina Komendantskaya, John Power

Research output: Chapter in Book/Report/Conference proceedingChapter

11 Citations (Scopus)
56 Downloads (Pure)

Abstract

Every variable-free logic program induces a Pf P f -coalgebra on the set of atomic formulae in the program. The coalgebra p sends an atomic formula A to the set of the sets of atomic formulae in the antecedent of each clause for which A is the head. In an earlier paper, we identified a variable-free logic program with a Pf P f -coalgebra on Set and showed that, if C(Pf P f ) is the cofree comonad on Pf P f , then given a logic program P qua Pf P f -coalgebra, the corresponding C(Pf P f )-coalgebra structure describes the parallel and-or derivation trees of P. In this paper, we extend that analysis to arbitrary logic programs. That requires a subtle analysis of lax natural transformations between Poset-valued functors on a Lawvere theory, of locally ordered endofunctors and comonads on locally ordered categories, and of coalgebras, oplax maps of coalgebras, and the relationships between such for locally ordered endofunctors and the cofree comonads on them
Original languageEnglish
Title of host publicationAlgebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchetser, UK, August 30 - September 2, 2011. Proceedings
EditorsAndrea Corradini, Bartek Kin, Corina Cirstea
Place of PublicationHeidelberg
PublisherSpringer
Pages268-282
Number of pages15
ISBN (Electronic)978-3-642-22944-2
ISBN (Print)978-3-22943-5
DOIs
Publication statusPublished - 2011
Event4th International Conference on Algebra and Coalgebra in Computer Science - Winchester, UK United Kingdom
Duration: 30 Aug 20112 Sep 2011

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume6859
ISSN (Print)0302-9743

Conference

Conference4th International Conference on Algebra and Coalgebra in Computer Science
Abbreviated titleCALCO 2011
CountryUK United Kingdom
CityWinchester
Period30/08/112/09/11

Fingerprint

Coalgebra
Logic Programming
Logic Programs
Ordered Categories
Semantics
Poset
Functor
Arbitrary

Cite this

Komendantskaya, E., & Power, J. (2011). Coalgebraic semantics for derivations in logic programming. In A. Corradini, B. Kin, & C. Cirstea (Eds.), Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchetser, UK, August 30 - September 2, 2011. Proceedings (pp. 268-282). (Lecture Notes in Computer Science; Vol. 6859). Heidelberg: Springer. https://doi.org/10.1007/978-3-642-22944-2_19

Coalgebraic semantics for derivations in logic programming. / Komendantskaya, Ekaterina; Power, John.

Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchetser, UK, August 30 - September 2, 2011. Proceedings. ed. / Andrea Corradini; Bartek Kin; Corina Cirstea. Heidelberg : Springer, 2011. p. 268-282 (Lecture Notes in Computer Science; Vol. 6859).

Research output: Chapter in Book/Report/Conference proceedingChapter

Komendantskaya, E & Power, J 2011, Coalgebraic semantics for derivations in logic programming. in A Corradini, B Kin & C Cirstea (eds), Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchetser, UK, August 30 - September 2, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6859, Springer, Heidelberg, pp. 268-282, 4th International Conference on Algebra and Coalgebra in Computer Science, Winchester, UK United Kingdom, 30/08/11. https://doi.org/10.1007/978-3-642-22944-2_19
Komendantskaya E, Power J. Coalgebraic semantics for derivations in logic programming. In Corradini A, Kin B, Cirstea C, editors, Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchetser, UK, August 30 - September 2, 2011. Proceedings. Heidelberg: Springer. 2011. p. 268-282. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-22944-2_19
Komendantskaya, Ekaterina ; Power, John. / Coalgebraic semantics for derivations in logic programming. Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchetser, UK, August 30 - September 2, 2011. Proceedings. editor / Andrea Corradini ; Bartek Kin ; Corina Cirstea. Heidelberg : Springer, 2011. pp. 268-282 (Lecture Notes in Computer Science).
@inbook{59d66ceea352493d8406e90ac7a855dc,
title = "Coalgebraic semantics for derivations in logic programming",
abstract = "Every variable-free logic program induces a Pf P f -coalgebra on the set of atomic formulae in the program. The coalgebra p sends an atomic formula A to the set of the sets of atomic formulae in the antecedent of each clause for which A is the head. In an earlier paper, we identified a variable-free logic program with a Pf P f -coalgebra on Set and showed that, if C(Pf P f ) is the cofree comonad on Pf P f , then given a logic program P qua Pf P f -coalgebra, the corresponding C(Pf P f )-coalgebra structure describes the parallel and-or derivation trees of P. In this paper, we extend that analysis to arbitrary logic programs. That requires a subtle analysis of lax natural transformations between Poset-valued functors on a Lawvere theory, of locally ordered endofunctors and comonads on locally ordered categories, and of coalgebras, oplax maps of coalgebras, and the relationships between such for locally ordered endofunctors and the cofree comonads on them",
author = "Ekaterina Komendantskaya and John Power",
year = "2011",
doi = "10.1007/978-3-642-22944-2_19",
language = "English",
isbn = "978-3-22943-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "268--282",
editor = "Andrea Corradini and Bartek Kin and Corina Cirstea",
booktitle = "Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchetser, UK, August 30 - September 2, 2011. Proceedings",

}

TY - CHAP

T1 - Coalgebraic semantics for derivations in logic programming

AU - Komendantskaya, Ekaterina

AU - Power, John

PY - 2011

Y1 - 2011

N2 - Every variable-free logic program induces a Pf P f -coalgebra on the set of atomic formulae in the program. The coalgebra p sends an atomic formula A to the set of the sets of atomic formulae in the antecedent of each clause for which A is the head. In an earlier paper, we identified a variable-free logic program with a Pf P f -coalgebra on Set and showed that, if C(Pf P f ) is the cofree comonad on Pf P f , then given a logic program P qua Pf P f -coalgebra, the corresponding C(Pf P f )-coalgebra structure describes the parallel and-or derivation trees of P. In this paper, we extend that analysis to arbitrary logic programs. That requires a subtle analysis of lax natural transformations between Poset-valued functors on a Lawvere theory, of locally ordered endofunctors and comonads on locally ordered categories, and of coalgebras, oplax maps of coalgebras, and the relationships between such for locally ordered endofunctors and the cofree comonads on them

AB - Every variable-free logic program induces a Pf P f -coalgebra on the set of atomic formulae in the program. The coalgebra p sends an atomic formula A to the set of the sets of atomic formulae in the antecedent of each clause for which A is the head. In an earlier paper, we identified a variable-free logic program with a Pf P f -coalgebra on Set and showed that, if C(Pf P f ) is the cofree comonad on Pf P f , then given a logic program P qua Pf P f -coalgebra, the corresponding C(Pf P f )-coalgebra structure describes the parallel and-or derivation trees of P. In this paper, we extend that analysis to arbitrary logic programs. That requires a subtle analysis of lax natural transformations between Poset-valued functors on a Lawvere theory, of locally ordered endofunctors and comonads on locally ordered categories, and of coalgebras, oplax maps of coalgebras, and the relationships between such for locally ordered endofunctors and the cofree comonads on them

UR - http://dx.doi.org/10.1007/978-3-642-22944-2_19

U2 - 10.1007/978-3-642-22944-2_19

DO - 10.1007/978-3-642-22944-2_19

M3 - Chapter

SN - 978-3-22943-5

T3 - Lecture Notes in Computer Science

SP - 268

EP - 282

BT - Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchetser, UK, August 30 - September 2, 2011. Proceedings

A2 - Corradini, Andrea

A2 - Kin, Bartek

A2 - Cirstea, Corina

PB - Springer

CY - Heidelberg

ER -