Semantics and Termination of Simply-Moded Logic Programs with Dynamic Scheduling

Sandro Etalle, Annalisa Bossi, Sabina Rossi, Jan-Georg Smaus

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    5 Citations (Scopus)
    54 Downloads (Pure)

    Abstract

    In logic programming, dynamic scheduling refers to a situation where the selection of the atom in each resolution (computation) step is determined at runtime, as opposed to a fixed selection rule such as the left-to-right one of Prolog. This has applications e.g. in parallel programming. A mechanism to control dynamic scheduling is provided in existing languages in the form of delay declarations. Input-consuming derivations were introduced to describe dynamic scheduling while abstracting from the technical details. We first formalise the relationship between delay declarations and input-consuming derivations, showing in many cases a one-to-one correspondence. Then, we define a model-theoretic semantics for input-consuming derivations of simply-moded programs. Finally, for this class of programs, we provide a necessary and sufficient criterion for termination.
    Original languageUndefined
    Title of host publication10th European Symp. on programming (ESOP)
    EditorsDavid Sands
    Place of PublicationBerlin
    PublisherSpringer
    Pages402-416
    Number of pages15
    ISBN (Print)3-540-41862-8
    DOIs
    Publication statusPublished - Apr 2001
    Event10th European Symposium on Programming, ESOP 2001 - Genova, Italy
    Duration: 2 Apr 20016 Apr 2001
    Conference number: 10

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer-Verlag
    Volume2028

    Conference

    Conference10th European Symposium on Programming, ESOP 2001
    Abbreviated titleESOP
    CountryItaly
    CityGenova
    Period2/04/016/04/01

    Keywords

    • IR-36869
    • METIS-203294
    • EWI-944

    Cite this