Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Determinism → (event structure isomorphism = step sequence equivalence)
Vaandrager F. Theoretical Computer Science79 (2):275-294,1991.Type:Article
Date Reviewed: Dec 1 1991

Vaandrager compares different notions of equivalence between deterministic event structures. The event structures are endowed with a causal relation that is a partial ordering; consequently, each event may be regarded as a prerequisite (and a successor) of itself, and no nontrivial event loops are possible. This greatly reduces the applicability of the results. It is also important to realize, as the author goes to great lengths to explain, that the notion of determinism used in the paper is not universal. For those readers who are more interested in the application of the results than in their formal derivation, this point is crucial. The author’s stance is that an event structure is deterministic if from each configuration, a given event causes a move to a unique next configuration. The paper does not consider structures in which a configuration may have two or more conflicting events enabled and there is a free choice of which is performed. The author argues that his definition is appropriate for modeling “reactive systems,” but even for such systems external stimuli are sometimes in conflict.

With these definitions, the author formulates different equivalence relations over his event structures--isomorphism, bisimulation, sequence equivalence, step sequence equivalence, pomset (partially ordered multiset) equivalence, and split sequence equivalence. He demonstrates their interrelationships and, in the deterministic case, shows that several of them coincide. The definition of an event structure includes an event labeling function about which little is said. This omission is a pity, since labelings rather than the actual events are often used in the figures.

The paper concludes with a discussion of how, for deterministic systems, concurrent actions may be split so that the causal structure can be deduced by an observer who can detect the start and finish of each event. Although the mathematics is presented in a slightly contracted form, the proofs are easy to follow, and the results are well cross-referenced to earlier work by others. This paper makes a useful but narrow contribution to the literature.

Reviewer:  D. J. Cooke Review #: CR115372
Bookmark and Share
 
Semantics Of Programming Languages (F.3.2 )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Semantics Of Programming Languages": Date
Contractions in comparing concurrency semantics
Kok J. (ed), Rutten J. Theoretical Computer Science 76(2-3): 179-222, 2001. Type: Article
Aug 1 1991
Abstract language design
Bradley L. Theoretical Computer Science 77(1-2): 5-26, 1990. Type: Article
Nov 1 1991
Correctness of concurrent processes
Olderog E. Theoretical Computer Science 80(2): 263-288, 1991. Type: Article
Dec 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy