Coalgebraic semantics for parallel derivation strategies in logic programming

Ekaterina Komendantskaya, Guy McCusker, John Power

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

    11 Citations (Scopus)

    Abstract

    Logic programming, a class of programming languages based on first-order logic, provides simple and efficient tools for goal-oriented proof-search. Logic programming supports recursive computations, and some logic programs resemble the inductive or coinductive definitions written in functional programming languages. In this paper, we give a coalgebraic semantics to logic programming. We show that ground logic programs can be modelled by either P-f P-f-coalgebras or P-f List-coalgebras on Set. We analyse different kinds of derivation strategies and derivation trees (proof-trees, SLD-trees, and-or parallel trees) used in logic programming, and show how they can be modelled coalgebraically.

    Original languageEnglish
    Title of host publicationAlgebraic Methodology and Software Technology
    Subtitle of host publication13th International Conference, AMAST 2010, Lac-Beauport, QC, Canada, June 23-25, 2010. Revised Selected Papers
    EditorsMichael Johnson, Dusko Pavlovic
    Place of PublicationBerlin
    PublisherSpringer
    Pages111-127
    Number of pages17
    ISBN (Electronic)9783642177965
    ISBN (Print)9783642177958
    DOIs
    Publication statusPublished - 2011
    Event13th International Conference on Algebraic Methodology and Software Technology - Lac Beauport, Canada
    Duration: 23 Jun 201025 Jun 2010
    http://mpc-amast2010.fsg.ulaval.ca/amast/

    Publication series

    NameLecture notes in computer science
    PublisherSpringer
    Volume6486

    Conference

    Conference13th International Conference on Algebraic Methodology and Software Technology
    Abbreviated titleAMAST2010
    CountryCanada
    CityLac Beauport
    Period23/06/1025/06/10
    Internet address

    Keywords

    • Logic programming
    • SLD-resolution
    • Parallel Logic programming
    • Coalgebra
    • Coinduction

    Cite this

    Komendantskaya, E., McCusker, G., & Power, J. (2011). Coalgebraic semantics for parallel derivation strategies in logic programming. In M. Johnson, & D. Pavlovic (Eds.), Algebraic Methodology and Software Technology: 13th International Conference, AMAST 2010, Lac-Beauport, QC, Canada, June 23-25, 2010. Revised Selected Papers (pp. 111-127). (Lecture notes in computer science; Vol. 6486). Springer . https://doi.org/10.1007/978-3-642-17796-5_7