Coalgebraic semantics for derivations in logic programming

Ekaterina Komendantskaya, John Power

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    15 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 languageEnglish
    Title of host publicationAlgebra and Coalgebra in Computer Science
    Subtitle of host publication4th International Conference, CALCO 2011, Winchester, UK, August 30 – September 2, 2011. Proceedings
    EditorsAndrea Corradini, Bartek Klin, Corina Cirstea
    Place of PublicationBerlin
    PublisherSpringer
    Pages268-282
    Number of pages15
    ISBN (Electronic)9783642229442
    ISBN (Print)9783642229435
    DOIs
    Publication statusPublished - 2011
    Event4th Conference on Algebra and Coalgebra in Computer Science - West Downs Centre of the University of Winchester., Winchester, United Kingdom
    Duration: 30 Aug 20112 Sep 2011
    http://calco2011.ecs.soton.ac.uk/

    Publication series

    NameLecture notes in computer science
    PublisherSpringer
    Volume6859
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference4th Conference on Algebra and Coalgebra in Computer Science
    Abbreviated titleCALCO 2011
    CountryUnited Kingdom
    CityWinchester
    Period30/08/112/09/11
    Internet address

    Keywords

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

    Fingerprint Dive into the research topics of 'Coalgebraic semantics for derivations in logic programming'. Together they form a unique fingerprint.

  • Research Output

    • 15 Citations
    • 1 Article

    Exploiting parallelism in coalgebraic logic programming

    Komendantskaya, E., Schmidt, M. & Heras, J., 28 Mar 2014, In : Electronic Notes in Theoretical Computer Science. 303, p. 121-148 28 p., ENTCS18421.

    Research output: Contribution to journalArticle

    Open Access
    File
  • 3 Citations (Scopus)
    274 Downloads (Pure)

    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