Partial order and contextual net semantics for atomic and locally atomic CC programs

Bueno Carrillo, Francisco and Hermenegildo, Manuel V. and Rossi, Francesca (1998). Partial order and contextual net semantics for atomic and locally atomic CC programs. "Science of Computer Programming", v. 30 (n. 1-2); pp. 51-82. ISSN 0167-6423. https://doi.org/10.1016/S0167-6423(97)00007-5.

Description

Title: Partial order and contextual net semantics for atomic and locally atomic CC programs
Author/s:
  • Bueno Carrillo, Francisco
  • Hermenegildo, Manuel V.
  • Rossi, Francesca
Item Type: Article
Título de Revista/Publicación: Science of Computer Programming
Date: January 1998
ISSN: 0167-6423
Volume: 30
Subjects:
Freetext Keywords: Concurrency, Constraints, Semantics, Concurrencia, Semántica
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (2MB) | Preview

Abstract

We present two concurrent semantics (i.e. semantics where concurrency is explicitely represented) for CC programs with atomic tells. One is based on simple partial orders of computation steps, while the other one is based on contextual nets and it is an extensión of a previous one for eventual CC programs. Both such semantics allow us to derive concurrency, dependency, and nondeterminism information for the considered languages. We prove some properties about the relation between the two semantics, and also about the relation between them and the operational semantics. Moreover, we discuss how to use the contextual net semantics in the context of CLP programs. More precisely, by interpreting concurrency as possible parallelism, our semantics can be useful for a safe parallelization of some CLP computation steps. Dually, the dependency information may also be interpreted as necessary sequentialization, thus possibly exploiting it for the task of scheduling CC programs. Moreover, our semantics is also suitable for CC programs with a new kind of atomic tell (called locally atomic tell), which checks for consistency only the constraints it depends on. Such a tell achieves a reasonable trade-off between efficiency and atomicity, since the checked constraints can be stored in a local memory and are thus easily accessible even in a distributed implementation.

More information

Item ID: 14267
DC Identifier: http://oa.upm.es/14267/
OAI Identifier: oai:oa.upm.es:14267
DOI: 10.1016/S0167-6423(97)00007-5
Official URL: http://www.sciencedirect.com/science/article/pii/S0167642397000075
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 15 Jan 2013 10:10
Last Modified: 21 Apr 2016 13:50
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM