We show that an orthogonal basis for a finite-dimensional Hilbert space can be equivalently characterised as a commutative †-Frobenius monoid in the category FdHilb, which has finite-dimensional Hilbert spaces as objects and continuous linear maps as morphisms, and tensor product for the monoidal structure. The basis is normalised exactly when the corresponding commutative †-Frobenius monoid is special. Hence, both orthogonal and orthonormal bases are characterised without mentioning vectors, but just in terms of the categorical structure: composition of operations, tensor product and the †-functor. Moreover, this characterisation can be interpreted operationally, since the †-Frobenius structure allows the cloning and deletion of basis vectors. That is, we capture the basis vectors by relying on their ability to be cloned and deleted. Since this ability distinguishes classical data from quantum data, our result has important implications for categorical quantum mechanics.

The papers included in this special issue of Mathematical Structures in Computer Science were selected from a larger set we solicited from leading research groups on both sides of the Atlantic. They cover a wide spectrum of tutorials, recent results and surveys in the area of lightweight and practical formal methods in the design and analysis of safety-critical systems. All the papers we received were submitted to a rigorous process of review and revision, based on which we made our final selection.

The scope of computation has expanded dramatically beyond the rubric of discrete, deterministic sequential computation under which it has been studied for many decades. That focus, of course, led to a great deal of deep and beautiful theory, but our focus in this special issue of Mathematical Structures in Computer Science is on new directions that have emerged from the study of computational phenomena in other settings, and thus on a celebration of the diversity of ideas, methods, new applications and novel sources of inspiration that have marked the modern era. The papers in this issue come from sources extending far beyond the core of computer science, yet using many of the central ideas that have evolved within computer science and mathematics. The nexus of all this activity has been, on the one hand, the boundary between logic and computation, and, on the other hand, the natural sciences, particularly physics and biology. The papers in this collection are expanded versions of selected papers from the DCM 2010 workshop, which was held in Edinburgh in July 2010. The theme of the workshop was Causality, Computation and Physics.

Frame and anti-frame rules have been proposed as proof rules for modular reasoning about programs. Frame rules allow the hiding of irrelevant parts of the state during verification, whereas the anti-frame rule allows the hiding of local state from the context.

We discuss the semantic foundations of frame and anti-frame rules, and present the first sound model for Charguéraud and Pottier's type and capability system including both of these rules. The model is a possible worlds model based on the operational semantics and step-indexed heap relations, and the worlds are given by a recursively defined metric space. We also extend the model to account for Pottier's generalised frame and anti-frame rules, where invariants are generalised to families of invariants indexed over preorders. This generalisation enables reasoning about some well-bracketed as well as (locally) monotone uses of local state.

We study monadic translations of the call-by-name (cbn) and call-by-value (cbv) fragments of the classical sequent calculus ${\overline{\lambda}\mu\tilde{\mu}}$ due to Curien and Herbelin, and give modular and syntactic proofs of strong normalisation. The target of the translations is a new meta-language for classical logic, named monadic λμ. This language is a monadic reworking of Parigot's λμ-calculus, where the monadic binding is confined to commands, thus integrating the monad with the classical features. Also, its μ-reduction rule is replaced by a rule expressing the interaction between monadic binding and μ-abstraction.

Our monadic translations produce very tight simulations of the respective fragments of ${\overline{\lambda}\mu\tilde{\mu}}$ within monadic λμ, with reduction steps of ${\overline{\lambda}\mu\tilde{\mu}}$ being translated in a 1–1 fashion, except for β steps, which require two steps. The monad of monadic λμ can be instantiated to the continuations monad so as to ensure strict simulation of monadic λμ within simply typed λ-calculus with β- and η-reduction. Through strict simulation, the strong normalisation of simply typed λ-calculus is inherited by monadic λμ, and then by cbn and cbv ${\overline{\lambda}\mu\tilde{\mu}}$, thus reproving strong normalisation in an elementary syntactical way for these fragments of ${\overline{\lambda}\mu\tilde{\mu}}$, and establishing it for our new calculus. These results extend to second-order logic, with polymorphic λ-calculus as the target, giving new strong normalisation results for classical second-order logic in sequent calculus style.

CPS translations of cbn and cbv ${\overline{\lambda}\mu\tilde{\mu}}$ with the strict simulation property are obtained by composing our monadic translations with the continuations-monad instantiation. In an appendix to the paper, we investigate several refinements of the continuations-monad instantiation in order to obtain in a modular way improvements of the CPS translations enjoying extra properties like simulation by cbv β-reduction or reduction of administrative redexes at compile time.

Mathematical logic and computer science have driven the design of a growing number of logics and related formalisms such as set theories and type theories. In response to this population explosion, logical frameworks have been developed as formal meta-languages in which to represent, structure, relate and reason about logics.

Research on logical frameworks has diverged into separate communities, often with conflicting backgrounds and philosophies. In particular, two of the most important logical frameworks are the framework of institutions, from the area of model theory based on category theory, and the Edinburgh Logical Framework LF, from the area of proof theory based on dependent type theory. Even though their ultimate motivations overlap – for example in applications to software verification – they have fundamentally different perspectives on logic.

In the current paper, we design a logical framework that integrates the frameworks of institutions and LF in a way that combines their complementary advantages while retaining the elegance of each of them. In particular, our framework takes a balanced approach between model theory and proof theory, and permits the representation of logics in a way that comprises all major ingredients of a logic: syntax, models, satisfaction, judgments and proofs. This provides a theoretical basis for the systematic study of logics in a comprehensive logical framework. Our framework has been applied to obtain a large library of structured and machine-verified encodings of logics and logic translations.

Indexed monoidal algebras are introduced as an equivalent structure for self-dual compact closed categories, and a coherence theorem is proved for the category of such algebras. Turing automata and Turing graph machines are defined by generalising the classical Turing machine concept so that the collection of such machines becomes an indexed monoidal algebra. On the analogy of the von Neumann data-flow computer architecture, Turing graph machines are proposed as potentially reversible low-level universal computational devices, and a truly reversible molecular size hardware model is presented as an example.

This paper introduces and studies a categorical analogue of the familiar monoid semiring construction. By introducing an axiomatisation of summation that unifies notions of summation from algebraic program semantics with various notions of summation from the theory of analysis, we demonstrate that the monoid semiring construction generalises to cases where both the monoid and the semiring are categories. This construction has many interesting and natural categorical properties, and natural computational interpretations.

We use constructions in monoid and group theory to exhibit an adjunction between the category of partially ordered monoids and lazy monoid homomorphisms and the category of partially ordered groups and group homomorphisms such that the unit of the adjunction is injective. We also prove a similar result for sets acted on by monoids and groups.

We introduce the new notion of a lazy homomorphism for a function f between partially ordered monoids such that f(m ○ m′) ≤ f(m) ○ f(m′).

Every monoid can be endowed with the discrete partial ordering (m ≤ m′ if and only if m=m′), so our constructions provide a way of embedding monoids into groups. A simple counterexample (the two-element monoid with a non-trivial idempotent) and some calculations show that one can never hope for such an embedding to be a monoid homomorphism, so the price paid for injecting a monoid into a group is that we must weaken the notion of a homomorphism to this new notion of a lazy homomorphism.

The computational significance of this is that a monoid is an abstract model of computation – or at least of ‘operations’ – and, similarly, a group models reversible computations/operations. With this reading, the adjunction with its injective unit gives a systematic high-level way of faithfully translating an irreversible system into a ‘lazy’ reversible one.

Informally, but perhaps informatively, we can describe this work as follows: we give an abstract analysis of how we can sensibly add ‘undo’ (in the sense of ‘control-Z’).

Guaranteeing that the parties of a network application respect a given protocol is a crucial issue. Session types offer a method for abstracting and validating structured communication sequences (sessions). Object-oriented programming is an established paradigm for large scale applications. Union types, which behave as the least common supertypes of a set of classes, allow the implementation of unrelated classes with similar interfaces without additional programming. We have previously developed an integration of the features above into a class-based core language for building network applications, and this successfully amalgamated sessions and methods so that data can be exchanged flexibly according to communication protocols (session types).

The first aim of the work reported in this paper is to provide a full proof of the type safety property for that core language by renewing syntax, typing and semantics. In this way, static typechecking guarantees that after a session has started, computation cannot get stuck on a communication deadlock.

The second aim is to define a constraint-based type system that reconstructs the appropriate session types of session declarations instead of assuming that session types are explicitly given by the programmer. Such an algorithm can save programming work, and automatically presents an abstract view of the communications of the sessions.

We propose a design and verification methodology supporting the early phases of system design for cooperative driver assistance systems, focusing on the realisability of new automotive functions. Specifically, we focus on applications where drivers are supported in complex driving tasks by safe strategies involving the coordinated movements of multiple vehicles to complete the driving task successfully. We propose a divide and conquer approach for formally verifying timed probabilistic requirements on successful completion of the driving task and collision freedom based on formal specifications of a set of given manoeuvring and communication capabilities of the car. In particular, this allows an assessment of whether they are sufficient to implement strategies for successful completion of the driving task.

We prove the decidability of the logic T→ of Ticket Entailment. This issue was first raised by Anderson and Belnap within the framework of relevance logic, and is equivalent to the question of the decidability of type inhabitation in simply typed combinatory logic with the partial basis BB′IW. We solve the equivalent problem of type inhabitation for the restriction of simply typed lambda calculus to hereditarily right-maximal terms.

The effective use of model-based formal methods in the development of complex embedded systems requires the integration of discrete-event models of controllers with continuous-time models of their environments. This paper proposes a new approach to the development of such combined models (co-models), in which an initial discrete-event model may include approximations of continuous-time behaviour that can subsequently be replaced by couplings to continuous-time models. An operational semantics of co-simulation allows the discrete and continuous models to run on their respective simulators and managed by a coordinating co-simulation engine. This permits the exploration of the composite co-model's behaviour in a range of operational scenarios. The approach has been realised using the Vienna Development Method (VDM) as the discrete-event formalism, and 20-sim as the continuous-time framework, and has been applied successfully to a case study based on the distributed controller for a personal transporter device.

In this paper we study the dynamics of entanglement in some hybrid qubit–qutrit systems under the influence of global, collective, local and multilocal depolarising noise. We show that depolarising noise can be used to induce entanglement. A critical point exists under every coupling of the system with the environment at which all the states are equally entangled. Furthermore, we show that no ESD occurs when either only the qubit is coupled to its local environment or the system is coupled to a multilocal or global environment. This is an important result for various quantum information processing tasks and thus merits further investigation.

We investigate the computing power of a restricted class of DNA strand displacement structures: those that are made of double strands with nicks (interruptions) in the top strand. To preserve this structural invariant, we impose restrictions on the single strands they interact with: we consider only two-domain single strands consisting of one toehold domain and one recognition domain. We study fork and join signal processing gates based on these structures, and show that these systems are amenable to formalisation and mechanical verification.

In this paper we extend the spectral order of Coecke and Martin to infinite-dimensional quantum states. Many properties present in the finite-dimensional case are preserved, but some of the most important are lost. The order is constructed and its properties analysed. Most of the useful measurements of information content are lost. Shannon entropy is defined on only a part of the model, and that part is not a closed subset of the model. The finite parts of the lattices used by Birkhoff and von Neumann as models for classical and quantum logic appear as subsets of the models for infinite classical and quantum states.

Non-interference guarantees the absence of illicit information flow throughout program execution. It can be enforced by appropriate information flow type systems. Much of the previous work on type systems for non-interference has focused on calculi or high-level programming languages, and existing type systems for low-level languages typically omit objects, exceptions and method calls. We define an information flow type system for a sequential JVM-like language that includes all these programming features, and we prove, in the Coq proof assistant, that it guarantees non-interference. An additional benefit of the formalisation is that we have extracted from our proof a certified lightweight bytecode verifier for information flow. Our work provides, to the best of our knowledge, the first sound and certified information flow type system for such an expressive fragment of the JVM.

There are advantages in the use of quantum computing in the elaboration of attacks on certain pseudorandom generators when compared with analogous attacks using classical computing. This paper presents a polynomial time quantum attack on the Blum–Micali generator, which is considered secure against threats from classical computers. The proposed attack uses a Grover inspired procedure together with the quantum discrete logarithm, and is able to recover previous and future outputs of the generator under attack, thereby completely compromising its unpredictability. The attack can also be adapted to other generators, such as Blum–Micali generators with multiple hard-core predicates and generators from the Blum–Micali construction, and also to scenarios where the requirements on the bits are relaxed. Such attacks represent a threat to the security of the pseudorandom generators adopted in many real-world cryptosystems.

This paper gives a bird's-eye view of the various ingredients that make up a modern, model-checking-based approach to performability evaluation: Markov reward models, temporal logics and continuous stochastic logic, model-checking algorithms, bisimulation and the handling of non-determinism. A short historical account as well as a large case study complete this picture. In this way, we show convincingly that the smart combination of performability evaluation with stochastic model-checking techniques, developed over the last decade, provides a powerful and unified method of performability evaluation, thereby combining the advantages of earlier approaches.

For any locally cartesian closed category ℰ, we prove that a local fibred right adjoint between slices of ℰ is given by a polynomial. The slices in question are taken in a well-known fibred sense.