P systems with active membranes are a class of bioinspired computing models, where the rules are used in the non-deterministic maximally parallel manner. In this paper, first, a new variant of timed P systems with active membranes is proposed, where the application of rules can be regulated by promoters with only two polarizations. Next, we prove that any Turing computable set of numbers can be generated by such a P system in the time-free way. Moreover, we construct a uniform solution to the $\mathcal{SAT}$ problem in the framework of such recognizer timed P systems in polynomial time, and the feasibility and effectiveness of the proposed system is demonstrated by an instance. Compared with the existing methods, the P systems constructed in our work require fewer necessary resources and RS-steps, which show that the solution is effective to NP-complete problem.

The concept of abstract data types (ADTs) has emerged in the last fifteen years or so as one of the major programming design tools, with the emphasis on modular construction of large-scale programe. ADTs provide the means for seperating how data objects may be used from the different ways in which they actually are, or might be, implemented. A foundation for the theory of compputation with ADTs must provide answers to such questions as: What are ADTs and how may they be specified? What does it mean to implement an ADT? How may we construct new ADTs from old ones? What does it mean to compute with ADTs? This paper is devoted to a new and rather general, constructively based approach to these questions.

In this paper we study subtyping for inductive types in dependent type theories in the framework of coercive subtyping. General structural subtyping rules for parameterised inductive types are formulated based on the notion of inductive schemata. Certain extensional equality rules play an important role in proving some of the crucial properties of the type system with these subtyping rules. In particular, it is shown that the structural subtyping rules are coherent and that transitivity is admissible in the presence of the functorial rules of computational equality.

A generalised framework of site graphs is introduced in order to provide the first fully semantic definition of the side-effect-free core of the rule-based language Kappa. This formalisation allows the use of types either to confirm that a rule respects a certain invariant or to guide a restricted refinement process that allows us to constrain its run-time applicability.

This paper presents a filter model for π-calculus and shows its full abstraction with respect to a ‘may’ operational semantics. The model is introduced in the form of a type assignment system. Types are related by a preorder that mimics the operational behaviour of terms. A subject expansion theorem holds. Terms are interpreted as filters of types: this interpretation is compositional. The proof of full abstraction relies on a notion of realizability of types and on the construction of terms, which test when an arbitrary term has a fixed type.

We continue our study of the negation-free structure of multiplicative linear logic, as represented by the structure of weakly distributive categories, to consider the ‘exponentials’! and ? in the weakly distributive context. In addition to the usual triple and cotriple structure that one would expect on each of the two operators, there must be some connection between them to replace the de Morgan relationship found in the linear logic context. This turns out to be the notion of tensorial strength. We analyze coherence for this situation, using a modification of the usual nets due to Danos, which is a form suitable for linear logic with exponentials but without negation.

This paper provides an abstract definition of a class of logics, called diagrammatic logics, together with a definition of morphisms and 2-morphisms between them. The definition of the 2-category of diagrammatic logics relies on category theory, mainly on adjunction, categories of fractions and limit sketches. This framework is applied to the formalisation of a parameterisation process. This process, which consists of adding a formal parameter to some operations in a given specification, is presented as a morphism of logics. Then the parameter passing process for recovering a model of the given specification from a model of the parameterised specification and an actual parameter is shown to be a 2-morphism of logics.

Action-labelled transition systems (LTSs) have proved to be a fundamental model for describing and proving properties of concurrent systems. In this paper we introduce Multiple-Labelled Transition Systems (MLTSs) as generalisations of LTSs that enable us to deal with system features that are becoming increasingly important when considering languages and models for network-aware programming. MLTSs enable us to describe not only the actions that systems can perform but also their usage of resources and their handling (creation, revelation . . .) of names; these are essential for modelling changing evaluation environments. We also introduce MoMo, which is a logic inspired by Hennessy–Milner Logic and the μ-calculus, that enables us to consider state properties in a distributed environment and the impact of actions and movements over the different sites. MoMo operators are interpreted over MLTSs and both MLTSs and MoMo are used to provide a semantic framework to describe two basic calculi for mobile computing, namely μKlaim and the asynchronous π-calculus.

Timed and register automata are well-known models of computation over timed and data words, respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes registers that can store data values for later comparison. Although these two models behave differently in appearance, several decision problems have the same (un)decidability and complexity results for both models. As a prominent example, emptiness is decidable for alternating automata with one clock or register, both with non-primitive recursive complexity. This is not by chance.

This work confirms that there is indeed a tight relationship between the two models. We show that a run of a timed automaton can be simulated by a register automaton over ordered data domain, and conversely that a run of a register automaton can be simulated by a timed automaton. These are exponential time reductions hold both in the finite and infinite words settings. Our results allow to transfer decidability results back and forth between these two kinds of models, as well complexity results modulo an exponential time reduction. We justify the usefulness of these reductions by obtaining new results on register automata.

In this paper we study approach structures on dcpo's. A dcpo (X, ≤) will be endowed with several other structures: the Scott topology; an approach structure generated by a collection of weightable quasi metrics on X; and a collection of weights corresponding to the quasi metrics. Understanding the interaction between these structures on X will eventually lead to some fixed-point theorems for the morphisms in the category of approach spaces, which are called contractions. Existing fixed-point theorems on both monotone and non-monotone maps are obtained as special cases.

We establish sufficient and necessary conditions for a natural sink to be a colimit in DCPO. Based on these conditions, we show how to construct a colimit for any functor F from a small category Ω into the category DCPO. This demonstrates that the category DCPO is cocomplete. We also investigate under what conditions the colimit object is algebraic.

Nominal sets are a sets-based first-order denotation for variables in logic and programming. In this paper we extend nominal sets to two-level nominal sets. These preserve much of the behaviour of nominal sets, including notions of variable and abstraction, but they include a denotation for both variables and meta-variables. Meta-variables are interpreted as infinite lists of distinct variable symbols. We use two-level sets to define, amongst other things, a denotation for meta-variable abstraction, and nominal style datatypes of syntax-with-binding with meta-variables. We discuss the connections between this and nominal terms and prove a soundness result.

Numerical computation is traditionally performed using floating-point arithmetic and truncated forms of infinite series, a methodology which allows for efficient computation at the cost of some accuracy. For most applications, these errors are entirely acceptable and the numerical results are considered trustworthy, but for some operations, we may want to have guarantees that the numerical results are correct, or explicit bounds on the errors. To obtain rigorous calculations, floating-point arithmetic is usually replaced by interval arithmetic and truncation errors are explicitly contained in the result. We may then ask the question of which mathematical operations can be implemented in a way in which the exact result can be approximated to arbitrary known accuracy by a numerical algorithm. This is the subject of computable analysis and forms a theoretical underpinning of rigorous numerical computation. The aim of this article is to provide a straightforward introduction to this subject that is powerful enough to answer questions arising in dynamic system theory.

Completeness is a key feature of abstract interpretation. It corresponds to exactness of the abstraction of fix-points and relies upon the need of absence of false alarms in static program analysis. Making abstract interpretation complete is therefore a major problem in approximating the semantics of programming languages. In this paper, we consider the problem of making abstract interpretations complete by minimally modifying the predicate transformer, i.e. the semantics, of a program. We study the mathematical properties of complete functions on complete lattices and prove the existence of minimal transformations of monotone functions to achieve completeness. We then apply minimal complete transformers to prove the minimality of standard program transformations in security, such as static program monitoring.

We present a formalisation in Agda of the theory of concurrent transitions, residuation and causal equivalence of traces for the π-calculus. Our formalisation employs de Bruijn indices and dependently typed syntax, and aligns the ‘proved transitions’ proposed by Boudol and Castellani in the context of CCS with the proof terms naturally present in Agda's representation of the labelled transition relation. Our main contributions are proofs of the ‘diamond lemma’ for the residuals of concurrent transitions and a formal definition of equivalence of traces up to permutation of transitions.

In the π-calculus, transitions represent propagating binders whenever their actions involve bound names. To accommodate these cases, we require a more general diamond lemma where the target states of equivalent traces are no longer identical, but are related by a braiding that rewires the bound and free names to reflect the particular interleaving of events involving binders. Our approach may be useful for modelling concurrency in other languages where transitions carry meta-data sensitive to particular interleavings, such as dynamically allocated memory addresses.

In this paper, we develop a general framework for continuous data representations using positive predicate structures. We first show that basic principles of Σ-definability which are used to investigate computability, i.e., existence of a universal Σ-predicate and an algorithmic characterization of Σ-definability hold on all predicate structures without equality. Then we introduce positive predicate structures and show connections between these structures and effectively enumerable topological spaces. These links allow us to study computability over continuous data using logical and topological tools.

In this paper, we consider a discrete-time quantum walk on the N-cycle governed by the condition that at every time step of the walk, the option persists, with probability p, of exercising a projective measurement on the coin degree of freedom. For a bipartite quantum system of this kind, we prove that the von Neumann entropy of the total density operator converges to its maximum value. Thus, when influenced by decoherence, the mutual information between the two subsystems corresponding to the space of the coin and the space of the walker must eventually diminish to zero. Put plainly, any level of decoherence greater than zero forces the system to become completely ‘disentangled’ eventually.

Harvey Friedman’s gap condition on embeddings of finite labelled trees plays an important role in combinatorics (proof of the graph minor theorem) and mathematical logic (strong independence results). In the present paper we show that the gap condition can be reconstructed from a small number of well-motivated building blocks: It arises via iterated applications of a uniform Kruskal theorem.

A general approach is proposed for transforming objects to methods on the fly in the framework of the π-calculus. The power of the approach is demonstrated by applying it to generate an encoding of the full lambda calculus in the π-calculus. The encoding is proved to preserve and reflect beta reduction, and is shown to be fully abstract with respect to Abramsky's applicative bisimilarity.

We will give a detailed account of why the simplicial sets model of the univalence axiom due to Voevodsky also models W-types. In addition, we will discuss W-types in categories of simplicial presheaves and an application to models of set theory.