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

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

doi:10.1007/3-540-45309-1_27

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 proceeding › Conference contribution › Academic › peer-review

5 Citations (Scopus)

113 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 language	Undefined
Title of host publication	10th European Symp. on programming (ESOP)
Editors	David Sands
Place of Publication	Berlin
Publisher	Springer
Pages	402-416
Number of pages	15
ISBN (Print)	3-540-41862-8
DOIs	https://doi.org/10.1007/3-540-45309-1_27
Publication status	Published - Apr 2001
Event	10th European Symposium on Programming, ESOP 2001 - Genova, Italy Duration: 2 Apr 2001 → 6 Apr 2001 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer-Verlag
Volume	2028

Conference

Conference	10th European Symposium on Programming, ESOP 2001
Abbreviated title	ESOP
Country/Territory	Italy
City	Genova
Period	2/04/01 → 6/04/01

Keywords

IR-36869
METIS-203294
EWI-944

Access to Document

10.1007/3-540-45309-1_27

semantics_-_bossi

Cite this

@inproceedings{ea9e339345e04781a5385a3568b1f33d,

title = "Semantics and Termination of Simply-Moded Logic Programs with Dynamic Scheduling",

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.",

keywords = "IR-36869, METIS-203294, EWI-944",

author = "Sandro Etalle and Annalisa Bossi and Sabina Rossi and Jan-Georg Smaus",

note = "Imported from DIES; 10th European Symposium on Programming, ESOP 2001 ; Conference date: 02-04-2001 Through 06-04-2001",

year = "2001",

month = apr,

doi = "10.1007/3-540-45309-1\_27",

language = "Undefined",

isbn = "3-540-41862-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "402--416",

editor = "David Sands",

booktitle = "10th European Symp. on programming (ESOP)",

address = "Germany",

}

Etalle, S, Bossi, A, Rossi, S & Smaus, J-G 2001, Semantics and Termination of Simply-Moded Logic Programs with Dynamic Scheduling. in D Sands (ed.), 10th European Symp. on programming (ESOP). Lecture Notes in Computer Science, vol. 2028, Springer, Berlin, pp. 402-416, 10th European Symposium on Programming, ESOP 2001, Genova, Italy, 2/04/01. https://doi.org/10.1007/3-540-45309-1_27

Semantics and Termination of Simply-Moded Logic Programs with Dynamic Scheduling. / Etalle, Sandro; Bossi, Annalisa; Rossi, Sabina et al.
10th European Symp. on programming (ESOP). ed. / David Sands. Berlin: Springer, 2001. p. 402-416 (Lecture Notes in Computer Science; Vol. 2028).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Etalle, Sandro

AU - Bossi, Annalisa

AU - Rossi, Sabina

AU - Smaus, Jan-Georg

N1 - Conference code: 10

PY - 2001/4

Y1 - 2001/4

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. 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.

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. 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.

KW - IR-36869

KW - METIS-203294

KW - EWI-944

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 - 10th European Symp. on programming (ESOP)

A2 - Sands, David

PB - Springer

CY - Berlin

T2 - 10th European Symposium on Programming, ESOP 2001

Y2 - 2 April 2001 through 6 April 2001

ER -