Dynamic Scheduling in Logic Programming

Title: Dynamic Scheduling in Logic Programming

Abstract: Dynamic scheduling is a concept in logic programming where the selection of the atom in each resolution (computation) step is determined at runtime, rather than following a fixed selection rule like the left-to-right one used in Prolog. This approach has applications in parallel programming and can improve efficiency in certain cases. Delay declarations are used to control dynamic scheduling in existing logic programming languages.

This study aims to formalize the relationship between delay declarations and input-consuming derivations, a method used to describe dynamic scheduling while abstracting from technical details. The authors also define a model-theoretic semantics for input-consuming derivations of simply-moded programs. Finally, they provide a necessary and sufficient criterion for termination, which is crucial for ensuring that programs with dynamic scheduling do not run indefinitely.

The research question at the heart of this study is: How can we ensure that logic programs with dynamic scheduling do not lead to non-terminating derivations, while still allowing for the flexibility and efficiency of dynamic scheduling?

The authors address this question by developing a method to control dynamic scheduling using delay declarations. They demonstrate that in many cases, there is a one-to-one correspondence between delay declarations and input-consuming derivations. They then define a model-theoretic semantics for input-consuming derivations and provide a necessary and sufficient criterion for termination, which helps to ensure that programs with dynamic scheduling do not run indefinitely.

The implications of this research are significant for the field of logic programming. It provides a clear method for controlling dynamic scheduling and ensuring termination in logic programs, which can lead to more efficient and effective programming in certain situations. Additionally, the research highlights the importance of understanding the relationship between delay declarations and input-consuming derivations, which can help programmers to write more effective logic programs.

Link to Article: https://arxiv.org/abs/0101022v1 Authors: arXiv ID: 0101022v1