On the Operational Semantics of Nondeterminism and Divergence

  1. (PDF, 498 KB)
AuthorSearch for: ; Search for: ; Search for:
Proceedings titleSemantics and Theory of Programming
ConferenceTheoretical Computer Science B: Logics, January 1996.
Volume160: 271-317
AbstractAn operational model of nondeterministic processes coupled with a novel theory of divergence is presented. The operational model represents internal nondeterminism without using explicit internal transitions. Here the notion of internal state effectively replaces the familiar notion of internal transition, giving rise to an alternative operational view of processes: the weak process. Roughly, a weak process is a collection of stable internal states together with a set of transitions each of which is defined from an internal state to another weak process. Internal nondeterminism arises from such refinement of processes into multiple internal states.A simple extension to the basic weak process model gives rise to an elaborate operational theory of divergence. According to this theory, the ability of a process to undertake an infinite internal computation which is pathological, or persistent, is distinguished from its ability to undertake an infinite internal computation which is not. Although applicable to process algebraic languages with an internal action construct, the resulting model is most suitable for supplying operational semantics to process algebras which express internal nondeterminism by an internal choice construct. The distinction between the two forms of divergence is in particular taken into account when the hiding construct of such a process algebra is assigned a weak process semantics.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number39184
NPARC number8913167
Export citationExport as RIS
Report a correctionReport a correction
Record identifier956a76ec-3741-453f-aaf0-49146ebc0966
Record created2009-04-22
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)
Date modified: