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

^*Corresponding author for this work

School of Computer Science

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

18 Citations (Scopus)

Abstract

Every variable-free logic program induces a P_f 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 P_f P _f -coalgebra on Set and showed that, if C(P_f P _f ) is the cofree comonad on P_f P _f , then given a logic program P qua P_f P _f -coalgebra, the corresponding C(P_f 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 language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Pages	268-282
Number of pages	15
Volume	6859 LNCS
DOIs	https://doi.org/10.1007/978-3-642-22944-2_19
Publication status	Published - 2011
Event	4th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2011 - Winchester, United Kingdom Duration: 30 Aug 2011 → 2 Sept 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6859 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	4th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2011
Country/Territory	United Kingdom
City	Winchester
Period	30/08/11 → 2/09/11

Keywords

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

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 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 6859 LNCS, pp. 268-282). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6859 LNCS). https://doi.org/10.1007/978-3-642-22944-2_19

Komendantskaya, Ekaterina ; Power, John. / Coalgebraic semantics for derivations in logic programming. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6859 LNCS 2011. pp. 268-282 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d254422bc5234695a117ec36c9fc77e7,

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.",

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

author = "Ekaterina Komendantskaya and John Power",

year = "2011",

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

language = "English",

isbn = "9783642229435",

volume = "6859 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "268--282",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

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

}

Komendantskaya, E & Power, J 2011, Coalgebraic semantics for derivations in logic programming. in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). vol. 6859 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6859 LNCS, pp. 268-282, 4th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2011, 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.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6859 LNCS 2011. p. 268-282 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6859 LNCS).

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 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.

KW - Coalgebra

KW - Lawvere theories

KW - Lax natural transformations

KW - Logic programming

KW - Oplax maps of coalgebras

KW - SLD-resolution

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

VL - 6859 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 268

EP - 282

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

T2 - 4th International Conference on Algebra and Coalgebra in Computer Science, CALCO 2011

Y2 - 30 August 2011 through 2 September 2011

ER -

Komendantskaya E, Power J. Coalgebraic semantics for derivations in logic programming. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol. 6859 LNCS. 2011. p. 268-282. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). 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

Fellowship CLANN EP/F044046/1: Computational Logic in Artificial Neural Networks

Cite this

Coalgebraic semantics for derivations in logic programming

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Fellowship CLANN EP/F044046/1: Computational Logic in Artificial Neural Networks

Cite this