We investigate several geometric models of networks that simultaneously have some nice global properties, including the small-diameter property, the small-community phenomenon, which is defined to capture the common experience that (almost) everyone in society also belongs to some meaningful small communities, and the power law degree distribution, for which our result significantly strengthens those given in van den Esker (2008) and Jordan (2010). These results, together with our previous work in Li and Peng (2011), build a mathematical foundation for the study of both communities and the small-community phenomenon in various networks.

In the proof of the power law degree distribution, we develop the method of alternating concentration analysis to build a concentration inequality by alternately and iteratively applying both the sub- and super-martingale inequalities, which seems to be a powerful technique with further potential applications.

In this paper we propose a novel approach for analysing proof nets of Multiplicative Linear Logic (MLL) using coding theory. We define families of proof structures called PS-families and introduce a metric space for each family. In each family:

1. (1) an MLL proof net is a true code element; and

2. (2) a proof structure that is not an MLL proof net is a false (or corrupted) code element.

The differential λ-calculus is a paradigmatic functional programming language endowed with a syntactical differentiation operator that allows the application of a program to an argument in a linear way. One of the main features of this language is that it is resource conscious and gives the programmer suitable primitives to handle explicitly the resources used by a program during its execution. The differential operator also allows us to write the full Taylor expansion of a program. Through this expansion, every program can be decomposed into an infinite sum (representing non-deterministic choice) of ‘simpler’ programs that are strictly linear.

The aim of this paper is to develop an abstract ‘model theory’ for the untyped differential λ-calculus. In particular, we investigate what form a general categorical definition of a denotational model for this calculus should take. Starting from the work of Blute, Cockett and Seely on differential categories, we develop the notion of a Cartesian closed differential category and prove that linear reflexive objects living in such categories constitute sound and complete models of the untyped differential λ-calculus. We also give sufficient conditions for Cartesian closed differential categories to model the Taylor expansion. This requires that every model living in such categories equates all programs having the same full Taylor expansion.

We then provide a concrete example of a Cartesian closed differential category modelling the Taylor expansion, namely the category MRel of sets and relations from finite multisets to sets. We prove that the extensional model of λ-calculus we have recently built in MRel is linear, and is thus also an extensional model of the untyped differential λ-calculus. In the same category, we build a non-extensional model and prove that it is, nevertheless, extensional on its differential part.

Finally, we study the relationship between the differential λ-calculus and the resource calculus, which is a functional programming language combining the ideas behind the differential λ-calculus with those behind Boudol's λ-calculus with multiplicities. We define two translation maps between these two calculi and study the properties of these translations. In particular, this analysis shows that the two calculi share the same notion of a model, and thus that the resource calculus can be interpreted by translation into every linear reflexive object living in a Cartesian closed differential category.

The spatial search problem consists of minimising the number of steps required to find a given site in a network, with the restriction that only an oracle query or a translation to a neighbouring site is allowed at each step. We propose a quantum algorithm for the spatial search problem on a triangular lattice with N sites and torus-like boundary conditions. The proposed algorithm is a special case of the general framework for abstract search proposed by Ambainis, Kempe and Rivosh (AKR) in Ambainis et al. (2005) and Tulsi in Tulsi (2008) applied to a triangular network. The AKR–Tulsi formalism was employed to show that the time complexity of the quantum search on the triangular lattice is .

Using the concept of a generalised priority constraint satisfaction problem, we previously found a way to introduce priority queries into fuzzy relational databases. The results were PFSQL (Priority Fuzzy Structured Query Language) together with a database independent interpreter for it. In an effort to improve the performance of the resolution of PFSQL queries, the aim of the current paper is to formalise PFSQL queries by obtaining their interpretation in an existing fuzzy logic. We have found that the ŁΠ logic provides sufficient elements. The SELECT line of PFSQL queries is semantically a formula of some fuzzy logic, and we show that such formulas can be naturally expressed in a conservative extension of the ŁΠ logic. Furthermore, we prove a theorem that gives the PSPACE containment for the complexity of finding a model for a given ŁΠ logic formula.