Triple graph grammars (TGGs) are a well-established concept for the specification and execution of bidirectional model transformations within model driven software engineering. Their main advantage is an automatic generation of operational rules for forward and backward model transformations, which simplifies specification and enhances usability as well as consistency. In this paper we present several important results for analysing model transformations based on the formal categorical foundation of TGGs within the framework of attributed graph transformation systems.

Our first main result shows that the crucial properties of correctness and completeness are ensured for model transformations. In order to analyse functional behaviour, we generate a new kind of operational rule, called a forward translation rule. We apply existing results for the analysis of local confluence for attributed graph transformation systems. As additional main results, we provide sufficient criteria for the verification of functional behaviour as well as a necessary and sufficient condition for strong functional behaviour. In fact, these conditions imply polynomial complexity for the execution of the model transformation. We also analyse information and complete information preservation of model transformations, that is, whether a source model can be reconstructed (uniquely) from the target model computed by the model transformation. We illustrate the results for the well-known model transformation example from class diagrams to relational database models.

This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced using such operations are of finite degree and automatic over the unary alphabet (that is, they can be described by finite automata over the unary alphabet). We investigate algorithmic properties of such unfolded graphs given their finite presentations. In particular, we ask whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another and whether the graph is connected. We give polynomial-time algorithms for each of these questions. For a fixed input graph, the algorithm for the first question is in constant time and the second question is decided using an automaton that recognises the reachability relation in a uniform way. Hence, we improve on previous work, in which non-elementary or non-uniform algorithms were found.

We give a constructive proof showing that every finitely generated polynomial ideal has a Gröbner basis, provided the ring of coefficients is Noetherian in the sense of Richman and Seidenberg. That is, we give a constructive termination proof for a variant of the well-known algorithm for computing the Gröbner basis. In combination with a purely order-theoretic result we have proved in a separate paper, this yields a unified constructive proof of the Hilbert basis theorem for all Noether classes: if a ring belongs to a Noether class, then so does the polynomial ring. Our proof can be seen as a constructive reworking of one of the classical proofs, in the spirit of the partial realisation of Hilbert's programme in algebra put forward by Coquand and Lombardi. The rings under consideration need not be commutative, but are assumed to be coherent and strongly discrete: that is, they admit a membership test for every finitely generated ideal. As a complement to the proof, we provide a prime decomposition for commutative rings possessing the finite-depth property.

A new correctness criterion for discriminating Proof Nets among Proof Structures of Multiplicative Linear Logic with the MIX rule is provided. This criterion is inspired by an original interpretation of Proof Structures as distributed systems, and logical formulae as processes. The computation inside a system corresponds to the logical flow of information inside a proof, that is, roughly speaking, a distributed version of Girard's token trip. Proof Nets are then characterised as deadlock free Proof Structures (deadlock free distributed systems). This result follows by explicitly considering the causal dependencies among logical formulae inside proofs, and it provides a new understanding of notions such as acyclicity, chains and empires in terms of concurrent computations.

Equational deduction is generalised within a category-based abstract model theory framework, and proved complete under a hypothesis of quantifier projectivity, using a semantic treatment that regards quantifiers as models rather than variables, and valuations as model morphisms rather than functions. Applications include many- and order-sorted (conditional) equational logics, Horn clause logic, equational deduction modulo a theory, constraint logics, and more, as well as any possible combination among them. In the cases of equational deduction modulo a theory and of constraint logic the completeness result is new. One important consequence is an abstract version of Herbrand's Theorem, which provides an abstract model theoretic foundation for equational and constraint logic programming.

The Hybrid system (Ambler et al. 2002b), implemented within Isabelle/HOL, allows object logics to be represented using higher order abstract syntax (HOAS), and reasoned about using tactical theorem proving in general, and principles of (co)induction in particular. The form of HOAS provided by Hybrid is essentially a lambda calculus with constants.

Of fundamental interest is the form of the lambda abstractions provided by Hybrid. The user has the convenience of writing lambda abstractions using names for the binding variables. However, each abstraction is actually a definition of a de Bruijn expression, and Hybrid can unwind the user's abstractions (written with names) to machine friendly de Bruijn expressions (without names). In this sense the formal system contains a hybrid of named and nameless bound variable notation.

In this paper, we present a formal theory in a logical framework, which can be viewed as a model of core Hybrid, and state and prove that the model is representationally adequate for HOAS. In particular, it is the canonical translation function from λ-expressions to Hybrid that witnesses adequacy. We also prove two results that characterise how Hybrid represents certain classes of λ-expression.

We provide the first detailed proof to be published that proper locally nameless de Bruijn expressions and α-equivalence classes of λ-expressions are in bijective correspondence. This result is presented as a form of de Bruijn representational adequacy, and is a key component of the proof of Hybrid adequacy.

The Hybrid system contains a number of different syntactic classes of expression, and associated abstraction mechanisms. Hence, this paper also aims to provide a self-contained theoretical introduction to both the syntax and key ideas of the system. Although this paper will be of considerable interest to those who wish to work with Hybrid in Isabelle/HOL, a background in automated theorem proving is not essential.

This paper initiates the study of a process algebra based on atomic actions that are assigned resources, and that supports true concurrency. By true concurrency we mean that the parallel composition of concurrent processes does not rely on an interleaving of concurrent actions for its definition. Our process algebra includes a number of interesting operators that can be defined using resources of atomic actions to control their behaviour: of particular note is a (weak) sequential composition operator that exploits the truly concurrent nature of the semantics; this operator extends significantly the operation of prefixing by atomic actions that is supported in most truly concurrent semantics. Our language also includes a parallel composition operator that allows local events to execute asynchronously, while requiring synchronising events to execute simultaneously. In addition, the language supports a restriction operator and includes (unguarded) recursion.

We present both a denotational semantics and a companion operational semantics for our language. The denotational semantics supports true concurrency, so that parallel composition is defined without non-determinism or interleaving. This semantics also is novel for its treatment of recursion. The meaning of a recursive process is defined using a least fixed point on a subdomain that is determined by the body of the recursion, and that varies from one process to another. Nonetheless, the recursion operators in the language have continuous interpretations in the denotational model. In fact, our denotational model is based on a domain-theoretic generalisation of Mazurkiewicz traces in which the concatenation operator, as well as the other operators from our language, can be given continuous interpretations.

The operational model is presented in a natural SOS style. We prove a congruence theorem relating the two semantics, which implies the operational model itself is compositional. The congruence theorem also implies the denotational model is adequate with respect to the operational semantics, and we characterise the relatively mild conditions under which the denotational semantics is fully abstract with respect to the operational semantics.

Dynamic programming is a strategy for solving optimisation problems. In this paper, we show how many problems that may be solved by dynamic programming are instances of the same abstract specification. This specification is phrased using the calculus of relations offered by topos theory. The main theorem underlying dynamic programming can then be proved by straightforward equational reasoning.

The generic specification of dynamic programming makes use of higher-order operators on relations, akin to the fold operators found in functional programming languages. In the present context, a data type is modelled as an initial F-algebra, where F is an endofunctor on the topos under consideration. The mediating arrows from this initial F-algebra to other F-algebras are instances of fold – but only for total functions. For a regular category ε, it is possible to construct a category of relations Rel(ε). When a functor between regular categories is a so-called relator, it can be extended (in some canonical way) to a functor between the corresponding categories of relations. Applied to an endofunctor on a topos, this process of extending functors preserves initial algebras, and hence fold can be generalised from functions to relations.

It is well-known that the use of dynamic programming is governed by the principle of optimality. Roughly, the principle of optimality says that an optimal solution is composed of optimal solutions to subproblems. In a first attempt, we formalise the principle of optimality as a distributivity condition. This distributivity condition is elegant, but difficult to check in practice. The difficulty arises because we consider minimum elements with respect to a preorder, and therefore minimum elements are not unique. Assuming that we are working in a Boolean topos, it can be proved that monotonicity implies distributivity, and this monotonicity condition is easy to verify in practice.

Computers are used extensively to simulate continuous dynamical systems. However, different conceptual and mathematical structures underlie discrete machines and continuous dynamics, so the question arises as to the ability of the computer to simulate or, more generally, to check the properties of a continuous system.

We discuss and compare two notions of stability for a continuous dynamical system, viz. shadowing and robustness, and relate them to both the practical and theoretical computability of the system. We first discuss what we can learn from the stability of a system, using a finite-precision machine. We then show, following the work in Collins (2005), that shadowing fails but robustness succeeds in ensuring the checkability of a reachability property.

Interaction nets have proved to be a useful tool for the study of computational aspects of various formalisms (e.g. λ-calculus, term rewriting systems), but they are also a programming paradigm in themselves, and this is actually how they were introduced by Lafont. In this paper we consider semi-simple interaction nets as a programming language, and present a type assignment system using intersection types. First we show that interactions preserve types (i.e., the system enjoys subject reduction), and we compare this type assignment system with the intersection systems for λ-calculus and term rewriting systems. Then we define a recursion scheme that ensures termination of all interaction sequences. By relaxing the scheme and using the type assignment system, we derive another sufficient condition for termination of interaction nets. Finally, we show that although the type system based on general intersection types is not decidable, its restriction to rank 2 types is, and we give an algorithm that computes principal types for nets.

The theory of algebraic module specifications and modular systems was developed initially mainly on the basis of equational algebraic specifications. We show that it is in fact almost independent of what kind of underlying specification framework is chosen. More specifically, we present a formulation where this framework appears as an indexed category or, equivalently, specification frame. The ensuing theory is called the theory of abstract module specifications. We are able to prove main results concerning the correctness and compositionality of abstract module specifications in a purely categorical way, assuming the existence of pushouts of morphisms between abstract specifications that allow model amalgamation, functor extension and/or suitable free constructions. Then, by instantiating the theory of abstract module specifications to the behaviour specification frame in the sense of Nivela and Orejas, we obtain a theory of behaviour module specifications.

This paper is concerned with the asymptotic properties of a restricted class of Petri nets equipped with stochastic mass-action semantics. We establish a simple algebraic criterion for the existence of an equilibrium, that is to say, an invariant probability that satisfies the detailed balance condition familiar from the thermodynamics of reaction networks. We also find that when such a probability exists, it can be described by a free energy function that combines an internal energy term and an entropy term. Under strong additional conditions, we show how the entropy term can be deconstructed using the finer-grained individual-token semantics of Petri nets.

Symmetric monoidal theories (SMTs) generalise algebraic theories in a way that make them suitable to express resource-sensitive systems, in which variables cannot be copied or discarded at will. In SMTs, traditional tree-like terms are replaced by string diagrams, topological entities that can be intuitively thought of as diagrams of wires and boxes. Recently, string diagrams have become increasingly popular as a graphical syntax to reason about computational models across diverse fields, including programming language semantics, circuit theory, quantum mechanics, linguistics, and control theory. In applications, it is often convenient to implement the equations appearing in SMTs as rewriting rules. This poses the challenge of extending the traditional theory of term rewriting, which has been developed for algebraic theories, to string diagrams. In this paper, we develop a mathematical theory of string diagram rewriting for SMTs. Our approach exploits the correspondence between string diagram rewriting and double pushout (DPO) rewriting of certain graphs, introduced in the first paper of this series. Such a correspondence is only sound when the SMT includes a Frobenius algebra structure. In the present work, we show how an analogous correspondence may be established for arbitrary SMTs, once an appropriate notion of DPO rewriting (which we call convex) is identified. As proof of concept, we use our approach to show termination of two SMTs of interest: Frobenius semi-algebras and bialgebras.

In this paper we define a logical framework, called &;lambda;TT, that is well suited for semantic analysis. We introduce the notion of a fibration [Lscr]1 : [Fscr]1 [xrarr ] [Cscr]1 being internally definableThe definability as used in this paper should not be confused with Bénabou's ‘definability’ (Bénabou 1985). in a fibration [Lscr]2 : [Fscr]2 [xrarr ] [Cscr]2. This notion amounts to distinguishing an internal category Lin [Lscr]2 and relating [Lscr]1 to the externalization of L through a pullback. When both [Lscr]1 and [Lscr]2 are term models of typed calculi [Lscr]1 and [Lscr]2, respectively, we say that [Lscr]1 is an internal typed calculus definable in the frame language [Lscr]2. We will show by examples that if an object language is adequately represented in λTT, then it is an internal typed calculus definable in the frame language λTT. These examples also show a general phenomenon: if the term model of an object language has categorical structure S, then an adequate encoding of the language in λTT imposes an explicit internal categorical structure S in the term model of λTT and the two structures are related via internal definability. Our categorical investigation of logical frameworks indicates a sensible model theory of encodings.

Mixins are modules that may contain deferred components, that is, components not defined in the module itself; moreover, in contrast to parameterised modules (like ML functors), they can be mutually dependent and allow their definitions to be overridden. In a preceding paper we defined a syntax and denotational semantics of a kernel language of mixin modules. Here, we take instead an axiomatic approach, giving a set of algebraic laws expressing the expected properties of a small set of primitive operators on mixins. Interpreting axioms as rewriting rules, we get a reduction semantics for the language and prove the existence of normal forms. Moreover, we show that the model defined in the earlier paper satisfies the given axiomatisation.

Linear logic (LL) has been used as a foundation (and inspiration) for the development of programming languages, logical frameworks, and models for concurrency. LL’s cut-elimination and the completeness of focusing are two of its fundamental properties that have been exploited in such applications. This paper formalizes the proof of cut-elimination for focused LL. For that, we propose a set of five cut-rules that allows us to prove cut-elimination directly on the focused system. We also encode the inference rules of other logics as LL theories and formalize the necessary conditions for those logics to have cut-elimination. We then obtain, for free, cut-elimination for first-order classical, intuitionistic, and variants of LL. We also use the LL metatheory to formalize the relative completeness of natural deduction and sequent calculus in first-order minimal logic. Hence, we propose a framework that can be used to formalize fundamental properties of logical systems specified as LL theories.

We present the dual to Birkhoff's variety theorem in terms of predicates over the carrier of a cofree coalgebra (that is, in terms of ‘coequations’). We then discuss the dual to Birkhoff's completeness theorem, showing how closure under deductive rules dualises to yield two modal operators acting on coequations. We discuss the properties of these operators and show that they commute. We prove as our main result the invariance theorem, which is the formal dual of Birkhoff's completeness theorem.

In this paper, we prove some embedding theorems for LTL (linear-time temporal logic) and its variants: viz. some generalisations, extensions and fragments of LTL. Using these embedding theorems, we give uniform proofs of the completeness, cut-elimination and/or decidability theorems for LTL and its variants. The proposed embedding theorems clarify the relationships between some LTL-variations (for example, LTL, a dynamic topological logic, a fixpoint logic, a spatial logic, Prior's logic, Davies' logic and an NP-complete LTL) and some traditional logics (for example, classical logic, intuitionistic logic and infinitary logic).

We develop bicategory theory in univalent foundations. Guided by the notion of univalence for (1-)categories studied by Ahrens, Kapulkin, and Shulman, we define and study univalent bicategories. To construct examples of univalent bicategories in a modular fashion, we develop displayed bicategories, an analog of displayed 1-categories introduced by Ahrens and Lumsdaine. We demonstrate the applicability of this notion and prove that several bicategories of interest are univalent. Among these are the bicategory of univalent categories with families and the bicategory of pseudofunctors between univalent bicategories. Furthermore, we show that every bicategory with univalent hom-categories is weakly equivalent to a univalent bicategory. All of our work is formalized in Coq as part of the UniMath library of univalent mathematics.

In this paper, we address the problem of proving confluence for string diagram rewriting, which was previously shown to be characterised combinatorially as double-pushout rewriting with interfaces (DPOI) on (labelled) hypergraphs. For standard DPO rewriting without interfaces, confluence for terminating rewriting systems is, in general, undecidable. Nevertheless, we show here that confluence for DPOI, and hence string diagram rewriting, is decidable. We apply this result to give effective procedures for deciding local confluence of symmetric monoidal theories with and without Frobenius structure by critical pair analysis. For the latter, we introduce the new notion of path joinability for critical pairs, which enables finitely many joins of a critical pair to be lifted to an arbitrary context in spite of the strong non-local constraints placed on rewriting in a generic symmetric monoidal theory.