1983-06-06
Compactness in semantics for merge and fair merge
Publication
Publication
An analysis of the role of compactness in defining the semantics of the merge and fair merge operations is provided. In a suitable context of hyperspaces (sets of subsets) a set is compact iff it is the limit of a sequence of finite sets; hence, compactness generalises bounded nondeterminacy. The merge operation is investigated in the setting of a simple language with elementary actions, sequential composition, nondeterministic choice and recursion. Metric topology is used as a framework to assign both a linear time and a branching time semantics to this language. It is then shown that the resulting meanings are compact trace sets and compact processes, respectively. This result complements previous work by De Bakker, Bergstra, Klop & Meyer. For the fair merge, an approach using scheduling through random choices is adopted — since a direct definition precludes the use of closed, let alone of compact sets. In the indirect approach, a compactness condition is used to show that the fair merge of two fair processes yields a fair process.
| Additional Metadata | |
|---|---|
| Springer | |
| doi.org/10.1007/3-540-12896-4_352 | |
| Logics of Programs | |
|
de Bakker, J., & Zucker, J. I. (1983). Compactness in semantics for merge and fair merge. In Lecture Notes in Computer Science (pp. 18–33). Springer. doi:10.1007/3-540-12896-4_352 |
|
