Coalgebraic semantics for derivations in logic programming

Ekaterina Komendantskaya; John Power

doi:10.1007/978-3-642-22944-2_19

Coalgebraic semantics for derivations in logic programming

Ekaterina Komendantskaya, John Power

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Citations (Scopus)

Abstract

Every variable-free logic program induces a P P -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 P P -coalgebra on Set and showed that, if C(P P ) is the cofree comonad on P P , then given a logic program P qua P P -coalgebra, the corresponding C(P P )-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 language	English
Title of host publication	Algebra and Coalgebra in Computer Science
Subtitle of host publication	4th International Conference, CALCO 2011, Winchester, UK, August 30 – September 2, 2011. Proceedings
Editors	Andrea Corradini, Bartek Klin, Corina Cirstea
Place of Publication	Berlin
Publisher	Springer
Pages	268-282
Number of pages	15
ISBN (Electronic)	9783642229442
ISBN (Print)	9783642229435
DOIs	https://doi.org/10.1007/978-3-642-22944-2_19
Publication status	Published - 2011
Event	4th Conference on Algebra and Coalgebra in Computer Science - West Downs Centre of the University of Winchester., Winchester, United Kingdom Duration: 30 Aug 2011 → 2 Sept 2011 http://calco2011.ecs.soton.ac.uk/

Publication series

Name	Lecture notes in computer science
Publisher	Springer
Volume	6859
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th Conference on Algebra and Coalgebra in Computer Science
Abbreviated title	CALCO 2011
Country/Territory	United Kingdom
City	Winchester
Period	30/08/11 → 2/09/11
Internet address	http://calco2011.ecs.soton.ac.uk/

Keywords

Logic programming
SLD-resolution
Coalgebra
Lawvere theories
Lax natural transformations
Oplax maps of coalgebras

Access to Document

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

Cite this

Komendantskaya, E., & Power, J. (2011). Coalgebraic semantics for derivations in logic programming. In A. Corradini, B. Klin, & C. Cirstea (Eds.), Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchester, UK, August 30 – September 2, 2011. Proceedings (pp. 268-282). (Lecture notes in computer science; Vol. 6859). Springer . 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, Winchester, UK, August 30 – September 2, 2011. Proceedings. editor / Andrea Corradini ; Bartek Klin ; Corina Cirstea. Berlin : Springer , 2011. pp. 268-282 (Lecture notes in computer science).

@inproceedings{a2e5f448e0a240948f26be0e8c3adff4,

title = "Coalgebraic semantics for derivations in logic programming",

abstract = "Every variable-free logic program induces a P P -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 P P -coalgebra on Set and showed that, if C(P P ) is the cofree comonad on P P , then given a logic program P qua P P -coalgebra, the corresponding C(P P )-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.",

keywords = "Logic programming, SLD-resolution, Coalgebra, Lawvere theories, Lax natural transformations, Oplax maps of coalgebras",

author = "Ekaterina Komendantskaya and John Power",

year = "2011",

doi = "10.1007/978-3-642-22944-2_19",

language = "English",

isbn = "9783642229435",

series = "Lecture notes in computer science",

publisher = "Springer ",

pages = "268--282",

editor = "Andrea Corradini and Bartek Klin and Corina Cirstea",

booktitle = "Algebra and Coalgebra in Computer Science",

note = "4th Conference on Algebra and Coalgebra in Computer Science, CALCO 2011 ; Conference date: 30-08-2011 Through 02-09-2011",

url = "http://calco2011.ecs.soton.ac.uk/",

}

Komendantskaya, E & Power, J 2011, Coalgebraic semantics for derivations in logic programming. in A Corradini, B Klin & C Cirstea (eds), Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchester, UK, August 30 – September 2, 2011. Proceedings. Lecture notes in computer science, vol. 6859, Springer , Berlin, pp. 268-282, 4th Conference on Algebra and Coalgebra in Computer Science, Winchester, United Kingdom, 30/08/11. 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, Winchester, UK, August 30 – September 2, 2011. Proceedings. ed. / Andrea Corradini; Bartek Klin; Corina Cirstea. Berlin: Springer , 2011. p. 268-282 (Lecture notes in computer science; Vol. 6859).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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 P P -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 P P -coalgebra on Set and showed that, if C(P P ) is the cofree comonad on P P , then given a logic program P qua P P -coalgebra, the corresponding C(P P )-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 P P -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 P P -coalgebra on Set and showed that, if C(P P ) is the cofree comonad on P P , then given a logic program P qua P P -coalgebra, the corresponding C(P P )-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.

KW - Logic programming

KW - SLD-resolution

KW - Coalgebra

KW - Lawvere theories

KW - Lax natural transformations

KW - Oplax maps of coalgebras

UR - http://www.scopus.com/inward/record.url?scp=80053000115&partnerID=8YFLogxK

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

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

M3 - Conference contribution

AN - SCOPUS:80053000115

SN - 9783642229435

T3 - Lecture notes in computer science

SP - 268

EP - 282

BT - Algebra and Coalgebra in Computer Science

A2 - Corradini, Andrea

A2 - Klin, Bartek

A2 - Cirstea, Corina

PB - Springer

CY - Berlin

T2 - 4th Conference on Algebra and Coalgebra in Computer Science

Y2 - 30 August 2011 through 2 September 2011

ER -

Komendantskaya E, Power J. Coalgebraic semantics for derivations in logic programming. In Corradini A, Klin B, Cirstea C, editors, Algebra and Coalgebra in Computer Science: 4th International Conference, CALCO 2011, Winchester, UK, August 30 – September 2, 2011. Proceedings. Berlin: Springer . 2011. p. 268-282. (Lecture notes in computer science). doi: 10.1007/978-3-642-22944-2_19

Coalgebraic semantics for derivations in logic programming

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Exploiting parallelism in coalgebraic logic programming

Cite this