Abstract abstract reduction

We propose novel algebraic proof techniques for rewrite systems. Church–Rosser theorems and further fundamental statements that do not mention termination are proved in Kleene algebra. Certain reduction and transformation theorems for termination that depend on abstract commutation, cooperation or simulation properties are proved in an extension with infinite iteration. Benefits of the algebraic approach are simple concise calculational proofs by equational reasoning, connection with automata-based decision procedures and a natural formal semantics for rewriting diagrams. It is therefore especially suited for mechanization and automation.     

Efficient Stochastic Simulation of Biological Systems with Multiple Variable Volumes

The application of concurrent calculi to the formalisation of biological systems constitutes a promising approach to the analysis in silico of biological phenomena. The Gillespie algorithm is one of the main models exploited for their stochastic simulation. While the original algorithm considers only one fixed-volume compartment, the simulation of biological systems often requires multi-compartment semantics. In this paper we present an enhanced formulation of an extended version of the algorithm which handles multiple compartments with varying volumes. The presented algorithm is used as basis for the implementation of an extension of the stochastic π-Calculus, called Sπ@, which allows an intuitive and concise formalisation of such systems. The algorithm is also efficient in presence of a high number of compartments and reactions, therefore Sπ@ represents the starting point for the development of an effective tool for the simulation of biological systems with dynamical structure even in presence of computationally expensive phenomena like diffusion.     

Secrecy and group creation

We add an operation of group creation to the typed π-calculus, where a group is a type for channels. Creation of fresh groups has the effect of statically preventing certain communications, and can block the accidental or malicious leakage of secrets. Intuitively, no channel belonging to a fresh group can be received by processes outside the initial scope of the group, even if those processes are untyped. We formalize this intuition by adapting a notion of secrecy introduced by Abadi, and proving a preservation of secrecy property.     

H∞ identification of “soft” uncertainty models

The paper investigates the problem of identifying uncertainty models of causal, SISO, LTI, discrete-time, BIBO stable, unknown systems, using frequency domain measurements corrupted by Gaussian noise of known covariance. Additive uncertainty models are looked for, consisting of a nominal model and an additive dynamic perturbation accounting for the modeling error. The nominal model is chosen within a class of affinely parametrized models with transfer function of given (possibly low) order. An estimate of the parameters minimizing the H_∞ modeling error is obtained by minimizing an upper bound of the worst-case (with respect to the modeling error) second moment of the estimation error. Then, a bound in the frequency domain guaranteeing to include, with probability α, the frequency response error between the estimated nominal model and the unknown system is derived.     

Probabilistic π-Calculus and Event Structures

This paper proposes two semantics of a probabilistic variant of the π-calculus: an interleaving semantics in terms of Segala automata and a true concurrent semantics, in terms of probabilistic event structures. The key technical point is a use of types to identify a good class of non-deterministic probabilistic behaviours which can preserve a compositionality of the parallel operator in the event structures and the calculus. We show an operational correspondence between the two semantics. This allows us to prove a “probabilistic confluence” result, which generalises the confluence of the linearly typed π-calculus.     

A Proof Search Specification of the π-Calculus

We present a meta-logic that contains a new quantifier (for encoding “generic judgments”) and inference rules for reasoning within fixed points of a given specification. We then specify the operational semantics and bisimulation relations for the finite π-calculus within this meta-logic. Since we restrict to the finite case, the ability of the meta-logic to reason within fixed points becomes a powerful and complete tool since simple proof search can compute this one fixed point. The quantifier helps with the delicate issues surrounding the scope of variables within π-calculus expressions and their executions (proofs). We shall illustrate several merits of the logical specifications we write: they are natural and declarative; they contain no side conditions concerning names of variables while maintaining a completely formal treatment of such variables; differences between late and open bisimulation relations are easy to see declaratively; and proof search involving the application of inference rules, unification, and backtracking can provide complete proof systems for both one-step transitions and for bisimulation.     

An algebraic approach to H∞ output feedback control problems

We derive an output feedback controller which stabilizes a system and satisfies a prescribed H_∞ norm bound of the closed loop transfer function. The proposed design method is available for any system, i.e. there are no restrictions on D₁₂ and D₂₁. This approach utilizes only algebraic operations, thus proofs are simple and clear.     

Linearity and bisimulation

Exploiting linear type structure, we introduce a new theory of weak bisimilarity for the π-calculus in which we abstract away not only τ-actions but also non-τ actions which do not affect well-typed observers. This gives a congruence far larger than the standard bisimilarity while retaining semantic soundness. The framework is smoothly extendible to other settings involving nondeterminism and state. As an application we develop a behavioural theory of secrecy in the π-calculus which ensures secure information flow for a strictly greater set of processes than the type-based approach, while still offering compositional verification techniques.