Abstract Petri nets form a concurrent model for distributed and asynchronous systems. They are capable of modeling information flow in a closed system, but are generally not suitable for the study of compositionality. We address the issue of Petri net compositionality by introducing extensional Petri nets. In an extensional Petri net some places are external while others are internal. Every external place is labeled by a distinguished interface name. When composing two extensional Petri nets two places with a same label are coerced. An external place can be turned into an internal place by applying localization operator. The paper takes a look at bisimulation semantics and observational properties of the extensional Petri nets.

Abstract. We propose an integration of structural subtyping with boolean con-nectives and semantic subtyping to define a Java-like programming language that exploits the benefits of both techniques. Semantic subtyping is an approach to defining subtyping relation based on set-theoretic models, rather than syntactic rules. On the one hand, this approach involves some non trivial mathematical machinery in the background. On the other hand, final users of the language need not know this machinery and the resulting subtyping relation is very powerful and intuitive. While semantic subtyping is naturally linked to the structural one, we show how the framework can also accommodate the nominal subtyping. Several examples show the expressivity and the practical advantages of our proposal. 1

Continuation-passing style (CPS) transforms have long been important tools in the study of programming. They have been shown to correspond to abstract machines and, when combined with a naming transform that expresses shared values, they enjoy a direct correspondence with encodings into process calculi such as the π-calculus. We present our notion of correctness and discuss the sufficient conditions that guarantee the correctness of transforms. We then consider the call-by-value, call-by-name and call-by-need evaluation strategies for the λ-calculus and present their CPS transforms, abstract machines, π-encodings, and proofs of correctness. Our analysis covers a uniform CPS transform, which differentiates the three evaluation strategies only by the treatment of function calls. This leads to a new CPS transform for call-by-need requiring a less expressive form of side effect, which we call constructive update.

We introduce a labelled transition semantics for the reversible π-calculus. It is the first account of a compositional definition of a reversible calculus, that has both concurrency primitives and name mobility. The notion of reversibility is strictly linked to the notion of causality. We discuss the notion of causality induced by our calculus, and we compare it with the existing notions in the literature, in particular for what concerns the syntactic feature of scope extrusion, typical of the π-calculus.

We define when a linear-time temporal property is a fairness property with respect to a given system. This captures the essence shared by most fairness assumptions that are used in the specification and verification of reactive and concurrent systems, such as weak fairness, strong fairness, k -fairness, and many others. We provide three characterizations of fairness: a language-theoretic, a game-theoretic, and a topological characterization. It turns out that the fairness properties are the sets that are “large” from a topological point of view, that is, they are the co-meager sets in the natural topology of runs of a given system. This insight provides a link to probability theory where a set is “large” when it has measure 1. While these two notions of largeness are similar, they do not coincide in general. However, we show that they coincide for ω -regular properties and bounded Borel measures. That is, an ω -regular temporal property of a finite-state system has measure 1 under a bounded Borel measure if and only if it is a fairness property with respect to that system. The definition of fairness leads to a generic relaxation of correctness of a system in linear-time semantics. We define a system to be fairly correct if there exists a fairness assumption under which it satisfies its specification. Equivalently, a system is fairly correct if the set of runs satisfying the specification is topologically large. We motivate this notion of correctness and show how it can be verified in a system.

We introduce the domain of continuous random variables (CRV) over a domain, as an alternative to Jones and Plotkin's probabilistic power domain. While no known Cartesian-closed category is stable under the latter, we show that the so-called thin (uniform) CRVs define a strong monad on the Cartesian-closed category of bc-domains. We also characterize their inequational theory, as (fair-)coin algebras. We apply this to solve a recent problem posed by M. Escardo: testing is semi-decidable for EPCF terms. CRVs arose from the study of the second author's (layered) Hoare indexed valuations, and we also make the connection apparent.

We motivate and study a generic relaxation of correctness of reactive and concurrent systems with respect to a temporal specification. We define a system to be fairly correct if there exists a fairness assumption under which it satisfies its specification. Equivalently, a system is fairly correct if the set of runs satisfying the specification is large from a topological point of view, i.e., it is a co-meager set. We compare topological largeness with its more popular sibling, probabilistic largeness, where a specification is probabilistically large if the set of runs satisfying the specification has probability 1. We show that topological and probabilistic largeness of omega-regular specifications coincide for bounded Borel measures on finite-state systems. As a corollary, we show that, for specifications expressed in LTL or by Buchi automata, checking that a finite-state system is fairly correct has the same complexity as checking that it is correct. Finally we study variants of the logics CTL and CTL*, where the 'for all runs' quantifier is replaced by a 'for a large set of runs' quantifier. We show that the model checking complexity for these variants is the same as for the original logics

We study the combination of probability and non-determinism from a categorical point of view. In category theory, non-determinism and probability are represented by suitable monads. However, these two monads do not combine well as they are. To overcome this problem, we introduce the notion of indexed valuations. This notion is used to define a new monad that can be combined with the usual non-deterministic monad via a categorical distributive law. We give an equational characterisation of our construction. We discuss the computational meaning of indexed valuations, and we show how they can be used by giving a denotational semantics of a simple imperative language.

Subtyping relations for the /spl pi/-calculus are usually defined in a syntactic way, by means of structural rules. We propose a semantic characterisation of channel types and use it to derive a subtyping relation. The type system we consider includes read-only and write-only channel types, as well as Boolean combinations of types. A set-theoretic interpretation of types is provided, in which Boolean combinations are interpreted as the corresponding set-theoretic operations. Subtyping is defined as inclusion of the interpretations. We prove the decidability of the subtyping relation and sketch the subtyping algorithm. In order to fully exploit the type system, we define a variant of the /spl pi/-calculus where communication is subjected to pattern matching that performs dynamic typecase.

This paper is about combining nondeterminism and probabilities. We study this phenomenon from a domain theoretic point of view. In domain theory, nondeterminism is modeled using the notion of powerdomain, while probability is modeled using the powerdomain of valuations. Those two functors do not combine well, as they are. We define the notion of powerdomain of indexed valuations, which can be combined nicely with the usual nondeterministic powerdomain. We show an equational characterization of our construction. Finally we discuss the computational meaning of indexed valuations, and we show how they can be used, by giving a denotational semantics of a simple imperative language.