Full Abstraction for a Shared Variable Parallel Language

Abstract

We give a new denotational semantics for a shared variable parallel programming language and prove full abstraction: the semantics gives identical meanings to commands if and only if they induce the same partial correctness behavior in all program contexts. The meaning of a command is a set of 'transition traces', which record the ways in which a command may interact with and be affected by its environment. We show how top modify the semantics to incorporate new program constructs, to allow for different levels of granularity or atomicity, and to model fair infinite computation, in each case achieving full abstraction with respect to an appropriate notion of program behavior.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1993
Accession Number
ADA263547

Entities

People

  • Stephen Brookes

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Inclusions
  • Language
  • Models
  • Neurobehavioral Manifestations
  • Programming Languages
  • Reasoning
  • Semantic Models
  • Semantics
  • Sequences
  • Standards
  • Test And Evaluation
  • Transitions

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Database Systems and Applications
  • Theoretical Analysis.