Fully abstract denotational semantics for flat Concurrent Prolog

R. Gerth; M. Codish; Yossi Lichtenstein; E. Shapiro

doi:10.1109/LICS.1988.5130

Fully abstract denotational semantics for flat Concurrent Prolog

R. Gerth, M. Codish, Yossi Lichtenstein, E. Shapiro

Research output: Contribution to conference › Paper › peer-review

24 Citations (Scopus)

Abstract

A denotational, hence, compositional semantics for a subset of Concurrent Prolog is developed and related to an operational semantics. The denotational semantics makes divergence and the resultant substitutions of finite computations together with the termination mode-success, failure, or deadlock-observable. Relative to this notion of observation it is proved that the denotational semantics is fully abstract in the sense that it records the minimal amount of extra information beyond the observables to make it compositional. Full abstraction is an important property because it quantifies the information that one needs in order to reason about individual program-parts independently. This is believed to be the first such result in the area of concurrent logic programming.

Original language	English
Pages	320-335
Number of pages	16
DOIs	https://doi.org/10.1109/LICS.1988.5130
Publication status	Published - Jul 1988
Event	3rd Annual Symposium on Logic in Computer Science (LICS) - Edinburgh, United Kingdom Duration: 5 Jul 1988 → 8 Jul 1988

Conference

Conference	3rd Annual Symposium on Logic in Computer Science (LICS)
Country/Territory	United Kingdom
City	Edinburgh
Period	5/07/88 → 8/07/88

Access to Document

10.1109/LICS.1988.5130

Cite this

@conference{bf3a3c70cb824f7d86123c476762ae17,

title = "Fully abstract denotational semantics for flat Concurrent Prolog",

abstract = "A denotational, hence, compositional semantics for a subset of Concurrent Prolog is developed and related to an operational semantics. The denotational semantics makes divergence and the resultant substitutions of finite computations together with the termination mode-success, failure, or deadlock-observable. Relative to this notion of observation it is proved that the denotational semantics is fully abstract in the sense that it records the minimal amount of extra information beyond the observables to make it compositional. Full abstraction is an important property because it quantifies the information that one needs in order to reason about individual program-parts independently. This is believed to be the first such result in the area of concurrent logic programming.",

author = "R. Gerth and M. Codish and Yossi Lichtenstein and E. Shapiro",

year = "1988",

month = jul,

doi = "10.1109/LICS.1988.5130",

language = "English",

pages = "320--335",

note = "3rd Annual Symposium on Logic in Computer Science (LICS) ; Conference date: 05-07-1988 Through 08-07-1988",

}

TY - CONF

T1 - Fully abstract denotational semantics for flat Concurrent Prolog

AU - Gerth, R.

AU - Codish, M.

AU - Lichtenstein, Yossi

AU - Shapiro, E.

PY - 1988/7

Y1 - 1988/7

N2 - A denotational, hence, compositional semantics for a subset of Concurrent Prolog is developed and related to an operational semantics. The denotational semantics makes divergence and the resultant substitutions of finite computations together with the termination mode-success, failure, or deadlock-observable. Relative to this notion of observation it is proved that the denotational semantics is fully abstract in the sense that it records the minimal amount of extra information beyond the observables to make it compositional. Full abstraction is an important property because it quantifies the information that one needs in order to reason about individual program-parts independently. This is believed to be the first such result in the area of concurrent logic programming.

AB - A denotational, hence, compositional semantics for a subset of Concurrent Prolog is developed and related to an operational semantics. The denotational semantics makes divergence and the resultant substitutions of finite computations together with the termination mode-success, failure, or deadlock-observable. Relative to this notion of observation it is proved that the denotational semantics is fully abstract in the sense that it records the minimal amount of extra information beyond the observables to make it compositional. Full abstraction is an important property because it quantifies the information that one needs in order to reason about individual program-parts independently. This is believed to be the first such result in the area of concurrent logic programming.

U2 - 10.1109/LICS.1988.5130

DO - 10.1109/LICS.1988.5130

M3 - Paper

SP - 320

EP - 335

T2 - 3rd Annual Symposium on Logic in Computer Science (LICS)

Y2 - 5 July 1988 through 8 July 1988

ER -