Coalgebraic Derivations in Logic Programming

E Komendantskaya, J Power

Research output: Chapter in Book/Report/Conference proceedingChapter

11 Citations (Scopus)
21 Downloads (Pure)

Abstract

Coalgebra may be used to provide semantics for SLD-derivations, both finite and infinite. We first give such semantics to classical SLD-derivations, proving results such as adequacy, soundness and completeness. Then, based upon coalgebraic semantics, we propose a new sound and complete algorithm for parallel derivations. We analyse this new algorithm in terms of the Theory of Observables, and we prove soundness, completeness, correctness and full abstraction results.
Original languageEnglish
Title of host publicationComputer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
EditorsM Bezem
Place of PublicationDagstuhl, Germany
PublisherLeibniz International Proceedings in Informatics
Pages352-366
Number of pages15
ISBN (Print)978-3-939897-32-3
DOIs
Publication statusPublished - Sep 2011

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl-Leibniz-Zentrum fuer Informatik

Fingerprint

Logic Programming
Soundness
Completeness
Coalgebra
Correctness
Semantics

Cite this

Komendantskaya, E., & Power, J. (2011). Coalgebraic Derivations in Logic Programming. In M. Bezem (Ed.), Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (pp. 352-366). (Leibniz International Proceedings in Informatics (LIPIcs)). Dagstuhl, Germany: Leibniz International Proceedings in Informatics. https://doi.org/10.4230/LIPIcs.CSL.2011.352

Coalgebraic Derivations in Logic Programming. / Komendantskaya, E; Power, J.

Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. ed. / M Bezem. Dagstuhl, Germany : Leibniz International Proceedings in Informatics, 2011. p. 352-366 (Leibniz International Proceedings in Informatics (LIPIcs)).

Research output: Chapter in Book/Report/Conference proceedingChapter

Komendantskaya, E & Power, J 2011, Coalgebraic Derivations in Logic Programming. in M Bezem (ed.), Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Leibniz International Proceedings in Informatics, Dagstuhl, Germany, pp. 352-366. https://doi.org/10.4230/LIPIcs.CSL.2011.352
Komendantskaya E, Power J. Coalgebraic Derivations in Logic Programming. In Bezem M, editor, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Dagstuhl, Germany: Leibniz International Proceedings in Informatics. 2011. p. 352-366. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.CSL.2011.352
Komendantskaya, E ; Power, J. / Coalgebraic Derivations in Logic Programming. Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. editor / M Bezem. Dagstuhl, Germany : Leibniz International Proceedings in Informatics, 2011. pp. 352-366 (Leibniz International Proceedings in Informatics (LIPIcs)).
@inbook{d9c7214be23c426bb89e6d709c44e9a6,
title = "Coalgebraic Derivations in Logic Programming",
abstract = "Coalgebra may be used to provide semantics for SLD-derivations, both finite and infinite. We first give such semantics to classical SLD-derivations, proving results such as adequacy, soundness and completeness. Then, based upon coalgebraic semantics, we propose a new sound and complete algorithm for parallel derivations. We analyse this new algorithm in terms of the Theory of Observables, and we prove soundness, completeness, correctness and full abstraction results.",
author = "E Komendantskaya and J Power",
note = "Computer Science Logic, 25th International Workshop / 20th Annual Conference of the EACSL, CSL 2011, September 12-15, 2011, Bergen, Norway.",
year = "2011",
month = "9",
doi = "10.4230/LIPIcs.CSL.2011.352",
language = "English",
isbn = "978-3-939897-32-3",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Leibniz International Proceedings in Informatics",
pages = "352--366",
editor = "M Bezem",
booktitle = "Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL",

}

TY - CHAP

T1 - Coalgebraic Derivations in Logic Programming

AU - Komendantskaya, E

AU - Power, J

N1 - Computer Science Logic, 25th International Workshop / 20th Annual Conference of the EACSL, CSL 2011, September 12-15, 2011, Bergen, Norway.

PY - 2011/9

Y1 - 2011/9

N2 - Coalgebra may be used to provide semantics for SLD-derivations, both finite and infinite. We first give such semantics to classical SLD-derivations, proving results such as adequacy, soundness and completeness. Then, based upon coalgebraic semantics, we propose a new sound and complete algorithm for parallel derivations. We analyse this new algorithm in terms of the Theory of Observables, and we prove soundness, completeness, correctness and full abstraction results.

AB - Coalgebra may be used to provide semantics for SLD-derivations, both finite and infinite. We first give such semantics to classical SLD-derivations, proving results such as adequacy, soundness and completeness. Then, based upon coalgebraic semantics, we propose a new sound and complete algorithm for parallel derivations. We analyse this new algorithm in terms of the Theory of Observables, and we prove soundness, completeness, correctness and full abstraction results.

UR - http://dx.doi.org/10.4230/LIPIcs.CSL.2011.352

U2 - 10.4230/LIPIcs.CSL.2011.352

DO - 10.4230/LIPIcs.CSL.2011.352

M3 - Chapter

SN - 978-3-939897-32-3

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 352

EP - 366

BT - Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL

A2 - Bezem, M

PB - Leibniz International Proceedings in Informatics

CY - Dagstuhl, Germany

ER -