Processes and the denotational semantics of concurrency
Information and ControlPublished 1 July 1982
J. W. de Bakker, J. I. Zucker
Citations277
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A framework allowing a unified and rigorous definition of the semantics of concurrency is proposed, which introduces processes as elements of process domains which are obtained as solutions of domain equations in the sense of Scott and Plotkin.
Abstract
The set of all probability measures with compact support on an ultrametric space can be endowed with a natural ultrametric.We show that the functor of probability measures with finite supports (respectively compact supports) forms a monad in the category of ultrametric spaces (respectively complete ultrametric spaces) and nonexpanding maps.It is also proven that the G-symmetric power functor has an extension onto the Kleisli category of the probability measure monad.
Keywords
Computer Science
The temporal logic of programs
5,586 Citations1977Amir Pnueli
A unified approach to program verification is suggested, which applies to both sequential and parallel programs, and the main proof method is that of temporal reasoning in which the time dependence of events is the basic concept.
IFIP CongressThe Semantics of a Simple Language for Parallel Programming.
2,116 Citations1974Gilles Kahn
A simple language for parallel programming is described and its mathematical properties are studied to make a case for more formal languages for systems programming and the design of operating systems.
Computer LanguagesDenotational semantics: The scott-strachey approach to programming language theory
1,237 Citations1983
Treats various kinds of languages, beginning with the pure-lambda-calculus and progressing through languages with states, commands, jumps, and assignments.
Lecture notes in computer scienceDomains for denotational semantics
726 Citations1982Dana Scott
This paper discusses many examples in an informal way that should serve as an introduction to the theory of domains and proves many things that were done previously axiomatically can now be proved in a straightfoward way as theorems.
SIAM Journal on ComputingA Powerdomain Construction
631 Citations1976Gordon Plotkin
A powerdomain construction is developed, which is analogous to the powerset construction and also fits in with the usual sum, product and exponentiation constructions on domains, and a restricted class of algebraic inductive partial orders is found which is closed under this construction.
SIAM Journal on ComputingData Types as Lattices
567 Citations1976Dana Scott
These spaces of “partial” objects are modeled in one universal domain, the set of all subsets of the integers, which renders the connection of this semantic theory with the ordinary theory of number theoretic functions clear and straightforward.
Communications of the ACMVerifying properties of parallel programs
543 Citations1976Susan Owicki, David Gries
A more powerful deductive system which is in some sense complete for partial correctness is defined, which provides for the use of auxiliary variables, which are added to a parallel program as an aid to proving it correct.
HAL (Le Centre pour la Communication Scientifique Directe)Coroutines and networks of parallel processes
480 Citations1976Gilles Kahn, David MacQueen
Ce langage de programmation permet aussi de clarifier les relations entre plusieurs concepts : coroutines, appel par necessite, structures de donnees dynamiques et calcul parallele.
Communications of the ACMDistributed processes
465 Citations1978Per Brinch Hansen
The paper gives several examples of distributed processes and shows that they include procedures, coroutines, classes, monitors, processes, semaphores, buffers, path expressions, and input/output as special cases.
Lecture notes in computer scienceCharacterizing correctness properties of parallel programs using fixpoints
337 Citations1980E. Allen Emerson, Edmund M. Clarke
It is shown that correctness properties of parallel programs can be described using computation trees and that from these descriptions fixpoint characterizations can be generated, and conditions on the form of computation tree descriptions to ensure that a correctness property can be characterized using continuous fixpoints are given.
ACM Transactions on Programming Languages and SystemsA Proof System for Communicating Sequential Processes
324 Citations1980Krzysztof R. Apt, Nissim Francez +1 more
An axiomatic proof system is presented for proving partial correctness and absence of deadlock of communicating sequential processes, the key (meta) rule introduces cooperation between proofs, and CSP's new convention for distributed termination of loops is dealt with.
The Denotational Description of Programming Languages
312 Citations1979Michael J. C. Gordon
Lecture notes in computer scienceScenarios: A model of non-determinate computation
227 Citations1981J. Dean Brock, William B. Ackerman
It is shown that history relations are a fundamentally incomplete characterization of non-determinate computation, and no extension exists, by constructing two networks which, though indistinguishable by history relations, cannot be substituted for each other in a larger network without changing the history relation of the larger network.
Journal of the ACMConcurrent Processes and Their Syntax
169 Citations1979George Milne, Robin Milner
It is shown that processes are a flow algebra, and therefore constitute a suitable semantics for flowgraphs, and it is emphasized that the nouon of flowgraph evolved from the notion of process and not the reverse.
Lecture notes in computer scienceFormal description of programming concepts
163 Citations1980Dines Bjørner
This invention relates to a method for forming metal battery terminals and to the terminals produced thereby for use with battery containers fabricated from thermally deformable materials such as polypropylene which involves casting the metal directly into place within and through the wall of such container.
Research Online (University of Wollongong)A model for communicating sequential process
155 Citations1980C. A. R. Hoare
A semantic model for processes based on failures is defined, which encapsulate certain finite aspects of process behaviour and allow an elegant treatment of nondeterminism, and a set of process operations are defined, including nondeterministic choice, conditional composition, and various forms of' parallel composition.
Studies in logic and the foundations of mathematicsProcesses: A Mathematical Model of Computing Agents
136 Citations1975Robin Milner
This chapter describes the concepts that may be useful in modeling the behavior of intercommunicating agents, together with some examples.
Fundamenta InformaticaeThe metric space of infinite trees. Algebraic and topological properties
107 Citations1980André Arnold, Maurice Nivat
On the composition of processes
103 Citations1982Vaughan Pratt
A model of net-connected processes is described that amounts to a reformulation of a model derived by Brock and Ackerman from the Kahn-McQueen model of processes as relations on streams of data, which leads directly to a straightforward definition of process composition.
Journal of the ACMFlowgraphs and Flow Algebras
94 Citations1979Robin Milner
It follows that the algebra of processes, which satisfies the laws of flow F, is a statable semanUcs for flowgraphs, there are, however, many other mterpretatmns of nets, some of which will be studied m subsequent papers.
Theoretical Computer ScienceMetric interpretations of infinite trees and semantics of non deterministic recursive programs
89 Citations1980André Arnold, Maurice Nivat
In this setting, the two main theorems of semantics of semantics are proved: equivalence between operational and denotational semantics and the one-many function computed by a program is the image of the set of trees computed by the program.
Denotational semantics of concurrency
71 Citations1982J. W. de Bakker, J. I. Zucker
A general framework for the denotational treatment of concurrency is introduced, using tools from metric topology as advocated by Nivat to solve this equation, and illustrating the approach with the definition of a variety of concepts as encountered in the study of concurrence.
Possible futures, acceptances, refusals, and communicating processes
65 Citations1981William C. Rounds, Stephen Brookes
The PF model can be mapped onto the AR model homomorphically, and the equivalence classes of this map can be characterized by imposing a very natural equivalence relation on the PF model.
Journal of the ACMFormal Justification of a Proof System for Communicating Sequential Processes
61 Citations1983Krzysztof R. Apt
Soundness and relative completeness of this proof system dealing with partial correctness of communicating sequential processes are proved and it is indicated in what way the semantics and the proof system can be extended to deal with the total correctness of the programs.
Theoretical Computer ScienceAn extensional treatment of dataflow deadlock
48 Citations1981William W. Wadge
A purely extensional (non operational) proof that no program passing the cycle sum test can ever deadlock is given, based on the notions of size (length) and completeness in the domain of histories.
Lecture notes in computer scienceAn operational semantics for pure dataflow
42 Citations1982A. A. Faustini
This paper proves the equivalence of an operational and a denotational semantics for pure dataflow, and it is proved that the operational behaviour of apure dataflow net is exactly described by the least fixed point solution to the net's associated set of equations.
Lecture notes in computer scienceTowards a mathematical theory of processes
34 Citations2006H. Bekić
A recent „mathematical” approach to the semantics of programming languages is extended to allow for quasi-parallel execution of processes, and a notion of „action” is proposed as a formalization of the kind of process involved, and various ways of action composition are studied.
DAIMI Report SeriesA Cook's Tour of Countable Nondeterminism
23 Citations1981Krzysztof R. Apt, Gordon Plotkin
Lecture notes in computer scienceSemantics of unbounded nondeterminism
22 Citations1980Ralph‐Johan Back
It is shown that the simple approach of taking the powerdomain of the flat cpo does not produce a correct semantics for programs in which nondeterminism is unbounded, and the power domain approach is extended to computation paths.
Lecture notes in computer scienceProof rules dealing with fairness
21 Citations1982Krzysztof R. Apt, Ernst-Rüdiger Olderog
Proof rules allowing to deal with two fairness assumptions in the context of Dijkstra's do-od programs by considering a translated version of the original program which uses random assignment x:=?
Lecture notes in computer scienceA sound and complete HOARE axiomatization of the ADA-rendezvous
14 Citations1982Rob Gerth
A HOARE-axiomatization is constructed for the ADA rendezvous, embedded in a subset of the ADA concurrency section, and it is proved to be sound and relatively complete.
Synchronization of Concurrent Processes
13 Citations1975Odd Pettersen
An overview of commonly used synchronization primitives and literature is given, and a new form of primitive expressing conditional critical regions is presented to the problem of "readers and writers", utilizing the proposed synchronization primitive.
SIAM Journal on ComputingOn the Existence of Cook Semantics
11 Citations1984Arie de Bruin
This paper shows for a simple language, the most sophisticated feature of which is that it has parameterless procedures, that the corresponding equations have a unique solution.