The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Our general motivation is to answer the question: “What is a model of concurrent computation?”. As a preliminary exercise, we study dataflow networks. We develop a very general notion of model for asynchronous networks. The “Kahn Principle”, which states that a network built from functional nodes is the least fixpoint of a system of equations associated with the network, has become a benchmark for...
We define a simple collection of operations for creating and manipulating record structures, where records are intended as finite associations of values to labels. A second-order type system over these operations supports both subtyping and polymorphism. We provide typechecking algorithms and limited semantic models. Our approach unifies and extends previous notions of records, bounded quantification,...
We define a concrete operational model of concurrent systems, called trace automata. For such automata, there is a natural notion of permutation equivalence of computation sequences, which holds between two computation sequences precisely when they represent two interleaved views of the “same concurrent computation.” Alternatively, permutation equivalence can be characterized in terms of a residual operation...
Together with A.W. Roscoe, the author has earlier presented two models (the Timed Stability Model and the Timed Failures-Stability Model) offering timed versions of Hoare's CSP. In this paper, the author outlines a hierarchy of untimed and timed models for CSP which includes the two above, and which allows one to reason about concurrent processes in a uniform fashion with the minimum of complexity...
A simple notion of specification is introduced, and a complete set of inference rules given, for reasoning about real-time processes. The notation of Timed Communicating Sequential Processes is employed, and the strongest possible specification of a process is discussed. A proof of correctness of a simple protocol is given to illustrate the method of verification.
We extend the failures/divergences model for CSP to include a component of infinite traces. This allows us to give a denotational semantics for a version of CSP including general nondeterministic choice and infinite hiding. Unfortunately the model is an incomplete partial order, so it is by no means obvious that the necessary fixed points exist. We have two proofs of this result, one via a congruence...
This paper presents an operational semantics for priority and fairness in occam. The semantics is based on the state transitions made by a transputer in the execution of an occam program. It is possible to abstract sufficiently from the transputer implementation that a clear semantics is produced but to maintain enough detail that the particular meanings intended for priority and fairness can be expressed...
We define the notion of an inductively defined type in the Calculus of Constructions and show how inductively defined types can be represented by closed types. We show that all primitive recursive functionals over these inductively defined types are also representable. This generalizes work by Böhm & Berarducci on synthesis of functions on term algebras in the second-order polymorphic λ-calculus...
Introducing meta-level access in a programming language is a delicate task, surrounded by threats of vicious circularity, infinite regress and unresolveable paradoxes on the one hand and triviality on the other hand. The reflective tower is one of the attempts to structure computational reflection, that is, access from a running process to its computational state. This paper gives the framework...
Assertional s-rings are introduced to provide an algebraic setting in which the finite and infinite behavior of nondeterministic programs can be expressed and reasoned about. This includes expressing the fair infinite behavior of nondeterministic iterative programs, and reasoning about termination under various fairness assumptions. We also address the question of when the reasoning techniques are...
We consider the semantics of algebraic specifications viewed as evolving rather than static entities. This leads to a relativization of final algebra semantics with respect to the space of evolutionary possibilities open to a given specification. The evolutionary space itself, which we call a language, has significant semantic content. The unit of application for our semantics is such a language of...
In this paper we introduce a process algebra which incorporates explicit representations of successful termination, deadlock and divergence, and analyze its semantic theory. We give both an operational and a denotational semantics for the language and show that they agree. The operational theory is based upon a suitable adaptation of the notion of bisimulation preorder. The denotational semantics...
In this paper we give a category-theoretic semantics for a simple imperative language featuring unbounded indeterminacy. This semantics satisfies the categorical analogues of continuity and has the meaning of while loops defined as colimits of ω-diagrams. Furthermore, it collapses via an abstraction function to a semantics that is fully abstract, and coincides with the operational semantics. The abstraction...
Huet has conjectured that the interpretations of a class of types (the “algebraic types”) in the PER model on the natural numbers for the second-order lambda calculus are in a certain sense the initial algebras. In this paper we examine several different PER models, and show that Huet's conjecture holds in each.
Recently, a new category of domains used for the mathematical foundations of denotational semantics, that of L-domains, has been under study. In this paper we consider a related category of posets, that of local lattices. First, a completion operator taking posets to local lattices is developed, and then this operator is extended to a functor from posets with embedding-projection pairs to local lattices...
The category of L-domains was discovered by A. Jung while solving the problem of finding maximal cartesian closed categories of algebraic CPO's and continuous functions. In this note we analyse properties of the lossless powerdomain construction, that is closed on the algebraic L-domains. The powerdomain is shown to be isomorphic to a collection of subsets of the domain on which the construction was...
Slightly modifying Burstall-Manna-Waldinger's Intermittent Assertions program verification method (also called SOMETIME method and denoted here by Bur), Sain[21] obtained the so called SOME OTHER TIME method and showed that it proves strictly more programs correct than the SOMETIME method and, on the other hand, proves less than or equally many programs correct as the method obtained from Bur by imposing...
We analyze recent work on an algebraic formulation for data refinement. Hoare's principal mathematical constructions are reviewed. Then, they are mildly reformulated and unified in terms of two principal category theoretic notions: those of an enriched category and monad, also known as a triple. The requisite definitions and theory are given, together with several examples to illustrate precisely...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.