Search

Petri nets are a graphical notation for describing a class of discrete event dynamic systems whose behaviours are characterised by concurrency, synchronisation, mutual exclusion and conflict. They have been used over the years for the modelling of various distributed systems applications. With the advent of pervasive systems and the Internet of Things, the Calculus of Context-aware Ambients (CCA) has emerged as a suitable formal notation for analysing the behaviours of these systems. In this paper, we are interested in comparing the expressive power of Petri nets to that of CCA. That is, can the class of systems represented by Petri nets be modelled in CCA? To answer this question, an algorithm is proposed that maps any Petri net onto a CCA process. We prove that a Petri net and its corresponding CCA process are behavioural equivalent. It follows that CCA is at least as expressive as Petri nets, i.e., any system that can be specified in Petri nets can also be specified in CCA. Moreover, tools developed for CCA can also be used to analyse the behaviours of Petri nets.

Petri nets are a graphical notation for describing a class of discrete event dynamic systems whose behaviours are characterised by concurrency, synchronisation, mutual exclusion and conflict. They have been used over the years for the modelling of various distributed systems applications. With the advent of pervasive systems and the Internet of Things, the Calculus of Context-aware Ambients (CCA) has emerged as a suitable formal notation for analysing the behaviours of these systems. In this paper, we are interested in comparing the expressive power of Petri nets to that of CCA. That is, can the class of systems represented by Petri nets be modelled in CCA? To answer this question, an algorithm is proposed that maps any Petri net onto a CCA process. We prove that a Petri net and its corresponding CCA process are behavioural equivalent. It follows that CCA is at least as expressive as Petri nets, i.e., any system that can be specified in Petri nets can also be specified in CCA. Moreover, tools developed for CCA can also be used to analyse the behaviours of Petri nets. [ABSTRACT FROM AUTHOR]

Existing models for the analysis of concurrent processes tend to focus on fail-stop failures, where processes are either working or permanently stopped, and their state (working/stopped) is known. In fact, systems are often affected by grey failures: failures that are latent, possibly transient, and may affect the system in subtle ways that later lead to major issues, such as crashes, limited availability or overload. We introduce a model of actor-based systems with grey failures, based on two interlinked layers: an actor model, given as an asynchronous process calculus with discrete time, and a failure model that represents failure patterns that can be injected into the system. Our failure model captures not only fail-stop node and link failures, but also grey failures, which might be partial or transient. We give a behavioural equivalence relation based on weak barbed bisimulation to compare systems on the basis of their ability to recover from failures, and on this basis we define some desirable properties of reliable systems. By doing so, we reduce the problem of checking reliability properties of systems to the problem of checking bisimulation. [ABSTRACT FROM AUTHOR]

• We present a fully abstract encoding of the lambda-calculus in the pi-calculus. • We apply a recent technique of unique solution of equations to establish completeness of the encoding. • We revisit the original encoding of the call-by-value lambda-calculus due to Milner, show some shortcomings, and study two approaches to overcome these shortcomings. We study Milner's encoding of the call-by-value λ -calculus into the π -calculus. We show that, by tuning the encoding to two subcalculi of the π -calculus (Internal π and Asynchronous Local π), the equivalence on λ -terms induced by the encoding coincides with Lassen's eager normal-form bisimilarity, extended to handle η -equality. As behavioural equivalence in the π -calculus we consider contextual equivalence and barbed congruence. We also extend the results to preorders. A crucial technical ingredient in the proofs is the recently-introduced technique of unique solutions of equations, further developed in this paper. In this respect, the paper also intends to be an extended case study on the applicability and expressiveness of the technique. [ABSTRACT FROM AUTHOR]

The fusion calculi are a simplification of the pi-calculus in which input and output are symmetric and restriction is the only binder. We highlight a major difference between these calculi and the pi-calculus from the point of view of types, proving some impossibility results for subtyping in fusion calculi. We propose a modification of fusion calculi in which the name equivalences produced by fusions are replaced by name preorders, and with a distinction between positive and negative occurrences of names. The resulting calculus allows us to import subtype systems, and related results, from the pi-calculus. We examine the consequences of the modification on behavioural equivalence (e.g., context-free characterisations of barbed congruence) and expressiveness (e.g., full abstraction of the embedding of the asynchronous pi-calculus). [ABSTRACT FROM AUTHOR]

Although different kinds of probabilistic π-calculus have been introduced and found their place in quantitative verification and evaluation, their behavioural equivalences still lack a deep investigation. We propose a simple probabilistic extension of the π-calculus, π, which is inspired by Herescu and Palamidessi's probabilistic asynchronous π-calculus. An early semantics of our π is presented. We generalise several classic behavioural equivalences to probabilistic versions, obtaining the probabilistic (strong) barbed equivalence and probabilistic bisimulation for π. Then we prove that the coincidence between the barbed equivalence and bisimilarity in the π-calculus is preserved in the probabilistic setting. [ABSTRACT FROM AUTHOR]

The paper investigates the capabilities for the improvement of network resources management through open access to Policy and Charging Control (PCC) in the Evolved Packet System. The open access allows 3rd party applications to access network functions through application programming interfaces (APIs). The paper suggests an approach to design APIs for open access to FCC. APIs implementation issues are considered. [ABSTRACT FROM AUTHOR]

Abstract: We present a process algebra called TiMo in which timeouts of interactions and adaptable migrations in a distributed environment with explicit locations can be specified. Timing constraints allow to control the communication between co-located mobile processes, and a migration action with variable destination supports flexible movement from one location to another. The model of time is based on local clocks rather than a global clock. We provide a structural translation of TiMo into behaviourally equivalent high level timed Petri nets. As a result, we obtain a formal net semantics for timed interaction and migration which is both structural and allows one to deal directly with concurrency and causality. [Copyright &y& Elsevier]

Abstract: The aim of the paper is to give a formal compositional semantics for spiking neural P systems (SNP systems) by following the Structural Operational Semantics (SOS) approach. A process algebra is introduced whose terms represent SNP systems. The algebra is equipped with a semantics, given as a labelled transition system. This semantics allows notions of behavioural equivalences over SNP systems to be studied. Some known equivalences are considered and their definition based on the given semantics is provided. Such equivalences are proved to be congruences. [Copyright &y& Elsevier]

Standard abstract model checking relies on abstract Kripke structures which approximate concrete models by gluing together indistinguishable states, namely by a partition of the concrete state space. Strong preservation for a specification language L amounts to the equivalence of concrete and abstract model checking of formulas in L. We show how abstract interpretation can be used to design generic abstract models that allow to view standard abstract Kripke structures as particular instances. Accordingly, strong preservation is generalized to abstract interpretation-based models and precisely related to the concept of completeness in abstract interpretation. The problem of minimally refining an abstract model in order to make it strongly preserving for some language L can be formulated as a minimal domain refinement in abstract interpretation in order to get completeness w.r.t. the logical/temporal operators of L. It turns out that this refined strongly preserving abstract model always exists and can be characterized as a greatest fixed point. As a consequence, some well-known behavioural equivalences, like bisimulation, simulation and stuttering, and their corresponding partition refinement algorithms can be elegantly characterized in abstract interpretation as completeness properties and refinements. [ABSTRACT FROM AUTHOR]

Abstract: We provide a classification of noninterference-based security properties for the formal analysis of secure information flow in concurrent and distributed systems. This is done in the setting of a process algebra modeling some Linda coordination primitives (asynchronous communication and read operation). For this purpose, we define relaxed notions of behavioural equivalence that take into account the observational power of the external observer. The resulting taxonomy is compared with analogous security definitions based on synchronous communication models, thus emphasizing the influence of the Linda coordination model upon the expressivity of the security properties, by giving a new intuition to the relative merits. [Copyright &y& Elsevier]

Abstract: We study the encoding of , the call-by-name -calculus enriched with McCarthy''s amb operator, into the -calculus. Semantically, amb is a challenging operator, for the fairness constraints that it expresses. We prove that, under a certain interpretation of divergence in the -calculus (weak divergence), a faithful encoding is impossible. However, with a different interpretation of divergence (strong divergence), the encoding is possible, and for this case we derive results and coinductive proof methods to reason about that are similar to those for the encoding of pure -calculi. We then use these methods to derive the most important laws concerning amb. We take bisimilarity as behavioural equivalence on the -calculus, which sheds some light on the relationship between fairness and bisimilarity. [Copyright &y& Elsevier]

Abstract: We present a compositional approach to defining expressive logics for coalgebras of endofunctors on . This approach uses a notion of language constructor and an associated notion of semantics to capture one inductive step in the definition of a language for coalgebras and of its semantics. We show that suitable choices for the language constructors and for their associated semantics yield logics which are both adequate and expressive w.r.t. behavioural equivalence. Moreover, we show that type-building operations give rise to corresponding operations both on language constructors and on their associated semantics, thus allowing the derivation of expressive logics for increasingly complex coalgebraic types. Our framework subsumes several existing approaches to defining logics for coalgebras, and at the same time allows the derivation of new logics, with logics for probabilistic systems being the prime example. [Copyright &y& Elsevier]

The main ideas underlying work on the model-theoretic foundations of algebraic specification and formal program development are presented in an informal way. An attempt is made to offer an overall view, rather than new results, and to focus on the basic motivation behind the technicalities presented elsewhere. [ABSTRACT FROM AUTHOR]