In this paper we present an operational semantics for the ‘call-by-name’ probabilistic λ-calculus, whose main feature is to use only deterministic relations and to have no constraint on the reduction strategy. The calculus enjoys similar properties to the usual λ-calculus. In particular we prove it to be confluent, and we prove a standardisation theorem.

The automorphism groups of types in several systems of type theory are studied. It is shown that in simply typed λ-calculus λ1βη and in its extension with surjective pairing and terminal object these groups correspond exactly to the groups of automorphisms of finite trees. In second-order λ-calculus and in Luo's framework (LF) with dependent products, any finite group may be represented.

This issue of Mathematical Structures in Computer Science (MSCS) contains a selection of papers presented at the 12th International Colloquium on Theoretical Aspects of Computing (ICTAC 2015), which took place in Cali, Colombia, on October 29–31, 2015.

This article continues the study of the definability in the local substructure $\mathcal{G}_{T,\omega}$ of the ω-Turing degrees, initiated in (Sariev and Ganchev 2014). We show that the class I of the intermediate degrees is definable in $\mathcal{G}_{T,\omega}$.

This volume collects together extended and improved versions of papers presented at the twentysecond Workshop on Logic, Language, Information and, Computation (WoLLIC 2015) held at the School of Informatics and Computing, Indiana University, Bloomington, Indiana. WoLLIC is an annual international forum on inter-disciplinary research involving formal logic, computing and programming theory, and natural language and reasoning. Each meeting includes invited talks and tutorials as well as contributed papers. Contributions were invited on all appropriate subjects of Logic, Language, Information, and Computation, with particular interest in cross-disciplinary topics.

We carry out a numerical study of the quantum walk search algorithm of Shenvi, Kempe and Whaley Shenvi et al. (2003) and the factors that affect its efficiency in finding an individual state from an unsorted set. Previous work has focused purely on the effects of the dimensionality of the dataset to be searched. In the current paper we consider the effects of interpolating between dimensions, the connectivity of the dataset and the possibility of disorder in the underlying substrate: all these factors affect the efficiency of the search algorithm. We show that in addition to the strong dependence on the spatial dimension of the structure to be searched, there are also secondary dependencies on the connectivity and symmetry of the lattice, with greater connectivity providing a more efficient algorithm. We also show that the algorithm can tolerate a non-trivial level of disorder in the underlying substrate.

We introduce a category of vector spaces modelling full propositional linear logic, similar to probabilistic coherence spaces and to Koethe sequences spaces. Its objects are rigged sequence spaces, Banach spaces of sequences, with norms defined from pairing with finite sequences, and morphisms are bounded linear maps, continuous in a suitable topology. The main interest of the work is that our model gives a realization of the free linear logic exponentials construction.

We present strategic port graph rewriting as a basis for the implementation of visual modelling tools. The goal is to facilitate the specification and programming tasks associated with the modelling of complex systems. A system is represented by an initial graph and a collection of graph rewrite rules, together with a user-defined strategy to control the application of rules. The traditional operators found in strategy languages for term rewriting have been adapted to deal with the more general setting of graph rewriting, and some new constructs have been included in the strategy language to deal with graph traversal and management of rewriting positions in the graph. We give a formal semantics for the language, and describe its implementation: the graph transformation and visualisation tool Porgy.

The genesis of this special issue was in a meeting that took place at Université Paris Diderot on December 15 and 16, 2016. Dale Miller, Professor at École polytechnique, had turned 60 a few days earlier. In a career spanning over three decades and in work conducted in collaboration with several students and colleagues, Dale had had a significant influence in an area that can be described as structural proof theory and its application to computation and reasoning. In recognition of this fact, several of his collaborators thought it appropriate to celebrate the occasion by organizing a symposium on topics broadly connected to his areas of interest and achievements. The meeting was a success in several senses: it was attended by over 35 people, there were 15 technical presentations describing new results, and, quite gratifyingly, we managed to spring the event as a complete surprise to Dale.

In this paper, we propose and explore a new approach to abstract machines and optimal reduction via streams, infinite sequences of elements. We first define a sequential abstract machine capable of performing directed virtual reduction (DVR) and then we extend it to its parallel version, whose equivalence is explained through the properties of DVR itself. The result is a formal definition of the λ-calculus interpreter called Parallel Environment for Lambda Calculus Reduction (PELCR), a software for λ-calculus reduction based on the Geometry of Interaction. In particular, we describe PELCR as a stream-processing abstract machine, which in principle can also be applied to infinite streams.

In this work, we continue our consideration of the constructions presented in the paper Krivine's Classical Realizability from a Categorical Perspective by Thomas Streicher. Therein, the author points towards the interpretation of the classical realizability of Krivine as an instance of the categorical approach started by Hyland. The present paper continues with the study of the basic algebraic set-up underlying the categorical aspects of the theory. Motivated by the search of a full adjunction, we introduce a new closure operator on the subsets of the stacks of an abstract Krivine structure that yields an adjunction between the corresponding application and implication operations. We show that all the constructions from ordered combinatory algebras to triposes presented in our previous work can be implemented, mutatis mutandis, in the new situation and that all the associated triposes are equivalent. We finish by proving that the whole theory can be developed using the ordered combinatory algebras with full adjunction or strong abstract Krivine structures as the basic set-up.

We study two well-known linear-time metrics on Markov chains (MCs), namely, the strong and strutter trace distances. Our interest in these metrics is motivated by their relation to the probabilistic linear temporal logic (LTL)-model checking problem: we prove that they correspond to the maximal differences in the probability of satisfying the same LTL and LTL−X (LTL without next operator) formulas, respectively.

The threshold problem for these distances (whether their value exceeds a given threshold) is NP-hard and not known to be decidable. Nevertheless, we provide an approximation schema where each lower and upper approximant is computable in polynomial time in the size of the MC.

The upper approximants are bisimilarity-like pseudometrics (hence, branching-time distances) that converge point-wise to the linear-time metrics. This convergence is interesting in itself, because it reveals a non-trivial relation between branching and linear-time metric-based semantics that does not hold in equivalence-based semantics.

This paper presents a simple and intuitive syntax for proof nets of the multiplicative cyclic fragment (McyLL) of linear logic (LL). The main technical achievement of this work is to propose a correctness criterion that allows for sequentialization (recovering a proof from a proof net) for all McyLL proof nets, including those containing cut links. This is achieved by adapting the idea of contractibility (originally introduced by Danos to give a quadratic time procedure for proof nets correctness) to cyclic LL. This paper also gives a characterization of McyLL proof nets for Lambek Calculus and thus a geometrical (i.e., non-inductive) way to parse phrases or sentences by means of Lambek proof nets.

Herbrand’s theorem is one of the most fundamental insights in logic. From the syntactic point of view, it suggests a compact representation of proofs in classical first- and higher-order logics by recording the information of which instances have been chosen for which quantifiers. This compact representation is known in the literature as Miller’s expansion tree proof. It is inherently analytic and hence corresponds to a cut-free sequent calculus proof. Recently several extensions of such proof representations to proofs with cuts have been proposed. These extensions are based on graphical formalisms similar to proof nets and are limited to prenex formulas.

In this paper, we present a new syntactic approach that directly extends Miller’s expansion trees by cuts and also covers non-prenex formulas. We describe a cut-elimination procedure for our expansion trees with cut that is based on the natural reduction steps and shows that it is weakly normalizing.

It has been known that categorical interpretations of dependent type theory with Σ- and Id-types induce weak factorization systems. When one has a weak factorization system $({\cal L},{\cal R})$ on a category $\mathbb{C}$ in hand, it is then natural to ask whether or not $({\cal L},{\cal R})$ harbors an interpretation of dependent type theory with Σ- and Id- (and possibly Π-) types. Using the framework of display map categories to phrase this question more precisely, one would ask whether or not there exists a class ${\cal D}$ of morphisms of $\mathbb{C}$ such that the retract closure of ${\cal D}$ is the class ${\cal R}$ and the pair $(\mathbb{C},{\cal D})$ forms a display map category modeling Σ- and Id- (and possibly Π-) types. In this paper, we show, with the hypothesis that $\cal{C}$ is Cauchy complete, that there exists such a class $\cal{D}$ if and only if $(\mathbb{C},\cal{R})$itself forms a display map category modeling Σ- and Id- (and possibly Π-) types. Thus, we reduce the search space of our original question from a potentially proper class to a singleton.

The notions of disintegration and Bayesian inversion are fundamental in conditional probability theory. They produce channels, as conditional probabilities, from a joint state, or from an already given channel (in opposite direction). These notions exist in the literature, in concrete situations, but are presented here in abstract graphical formulations. The resulting abstract descriptions are used for proving basic results in conditional probability theory. The existence of disintegration and Bayesian inversion is discussed for discrete probability, and also for measure-theoretic probability – via standard Borel spaces and via likelihoods. Finally, the usefulness of disintegration and Bayesian inversion is illustrated in several examples.

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.

Differential categories are now an established abstract setting for differentiation. However, not much attention has been given to the process which is inverse to differentiation: integration. This paper presents the parallel development for integration by axiomatizing an integral transformation, sA: !A → !A ⊗ A, in a symmetric monoidal category with a coalgebra modality. When integration is combined with differentiation, the two fundamental theorems of calculus are expected to hold (in a suitable sense): a differential category with integration which satisfies these two theorems is called a calculus category.

Modifying an approach to antiderivatives by T. Ehrhard, we define having antiderivatives as the demand that a certain natural transformation, K: !A → !A, is invertible. We observe that a differential category having antiderivatives, in this sense, is always a calculus category.

When the coalgebra modality is monoidal, it is natural to demand an extra coherence between integration and the coalgebra modality. In the presence of this extra coherence, we show that a calculus category with a monoidal coalgebra modality has its integral transformation given by antiderivatives and, thus, that the integral structure is uniquely determined by the differential structure.

The paper finishes by providing a suite of separating examples. Examples of differential categories, integral categories and calculus categories based on both monoidal and (mere) coalgebra modalities are presented. In addition, differential categories which are not integral categories are discussed and vice versa.

Motivated by the need to reason about hybrid systems, we study limits in categories of coalgebras whose underlying functor is a Vietoris polynomial one – intuitively, the topological analogue of a Kripke polynomial functor. Among other results, we prove that every Vietoris polynomial functor admits a final coalgebra if it respects certain conditions concerning separation axioms and compactness. When the functor is restricted to some of the categories induced by these conditions, the resulting categories of coalgebras are even complete.

As a practical application, we use these developments in the specification and analysis of non-deterministic hybrid systems, in particular to obtain suitable notions of stability and behaviour.

The paper shows how the Scott–Koymans theorem for the untyped λ-calculus can be extended to the differential λ-calculus. The main result is that every model of the untyped differential λ-calculus may be viewed as a differential reflexive object in a Cartesian-closed differential category. This extension of the Scott–Koymans theorem depends critically on unraveling the somewhat subtle issue of which idempotents can be split so that differential structure lifts to the idempotent splitting.

The paper uses (total) Turing categories with “canonical codes” as the basic categorical semantics for the λ-calculus. It develops the main result in a modular fashion by showing how to add left-additive structure to a Turing category, and then – on top of that – differential structure. For both levels of structure, it is necessary to identify how “canonical codes” must behave with respect to the added structure and, furthermore, how “universal objects” must behave. The latter is closely tied to the question – which is the crux of the paper – of which idempotents can be split while preserving the differential structure of the setting.

This paper is the full version of a conference paper and includes the proofs which were omitted from that version due to page-length restrictions.