TY - GEN
T1 - Semantics and termination of simply-moded logic programs with dynamic scheduling
AU - Bossi, A.
AU - Etalle, S.
AU - Rossi, S.
AU - Smaus, J.G.
PY - 2001
Y1 - 2001
N2 - 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. In this paper, we first formalize 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.
AB - 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. In this paper, we first formalize 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.
U2 - 10.1007/3-540-45309-1_27
DO - 10.1007/3-540-45309-1_27
M3 - Conference contribution
SN - 3-540-41862-8
T3 - Lecture Notes in Computer Science
SP - 402
EP - 416
BT - Programming languages and systems : proceedings 10th European symposium on programming, ESOP 2001, held as part of the joint European conferences on theory and practice of software, ETAPS 2001, Genova, Italy, april 2-6, 2001
A2 - Sands, D.
PB - Springer
ER -