Practical computers have only finite amounts of memory. However, the programs that run on them are often written in languages that effectively assume (via providing constructs such as general recursion) that infinite memory is available, meaning that an implementation of those programs is necessarily an approximation. The main focus of this thesis is on the use of contraction: the ability to use a function parameter more than once in the body of that function (or more generally, to mention a free variable more than once in a term). Unrestricted contraction is a common reason for a language to require unbounded amounts of memory to implement. This thesis looks at a range of type systems, both existing and new, that restrict the use of contraction so that they can be implemented with finite amounts of state, identifying common themes, and explaining and suggesting solutions for common deficiencies. In particular, different restrictions on contraction are seen to correspond to different features of the language’s implementation.

Evolution is notorious for its creative power, but also for giving rise to complex, unpredictable dynamics. As a result, practitioners of artificial evolution have encountered difficulties in predicting, analysing, or even understanding the outcome of their experiments. In particular, the concept of evolutionary "progress" (whether in the sense of performance increase or complexity growth) has given rise to much debate and confusion. After a careful description of the mechanisms of evolution and natural selection, we provide usable concepts of performance and progress in coevolution. In particular, we introduce a distinction between three types of progress: local, historical, and global, which we suggest underlies much of the confusion that surrounds coevolutionary dynamics. Similarly, we provide a comprehensive answer to the question of whether an "arrow of complexity" exists in evolution. We introduce several methods to detect and analyse performance and progress in coevolutionary experiments. We propose a statistical measure (Fitness Transmission) to detect the presence of adaptive Darwinian evolution in a reproducing population, based solely on genealogic records; we also point out the limitations of a popular method (the Bedau-Packard statistics of evolutionary activity) for this purpose. To test and illustrate our results, we implement a rich experimental system, inspired by the seminal work of Karl Sims, in which virtual creatures can evolve and interact under various conditions in a physically realistic three-dimensional (3D) environment. To our knowledge, this is the first complete reimplementation and extension of Sims' results. We later extend this system with the introduction of physical combat between creatures, also a first. Finally, we introduce Evosphere, an open, planet-like environment in which 3D artificial creatures interact, reproduce and evolve freely. We conclude our discussion by using Fitness Transmission to detect the onset of adaptive evolution in this system.

We investigate partial functions and computability theory from within a constructive, univalent type theory. The focus is on placing computability into a larger mathematical context, rather than on a complete development of computability theory. We begin with a treatment of partial functions, using the notion of dominance, which is used in synthetic domain theory to discuss classes of partial maps. We relate this and other ideas from synthetic domain theory to other approaches to partiality in type theory. We show that the notion of dominance is difficult to apply in our setting: the set of �0 1 propositions investigated by Rosolini form a dominance precisely if a weak, but nevertheless unprovable, choice principle holds. To get around this problem, we suggest an alternative notion of partial function we call disciplined maps. In the presence of countable choice, this notion coincides with Rosolini’s. Using a general notion of partial function,we take the first steps in constructive computability theory. We do this both with computability as structure, where we have direct access to programs; and with computability as property, where we must work in a program-invariant way. We demonstrate the difference between these two approaches by showing how these approaches relate to facts about computability theory arising from topos-theoretic and typetheoretic concerns. Finally, we tie the two threads together: assuming countable choice and that all total functions N - N are computable (both of which hold in the effective topos), the Rosolini partial functions, the disciplined maps, and the computable partial functions all coincide. We observe, however, that the class of all partial functions includes non-computable partial functions.

Mobile notifications provide a unique mechanism for real-time information delivery systems to users in order to increase its effectiveness. However, real-time notification delivery to users via mobile phones does not always translate into users' awareness about the delivered information because these alerts might arrive at inappropriate times and situations. Moreover, notifications that demand users' attention at inopportune moments are more likely to have adverse effects and become a cause of potential disruption rather than proving beneficial to users. In order to address these challenges it is of paramount importance to devise intelligent notification mechanisms that monitor and learn users' behaviour for maximising their receptivity to the delivered information and adapt accordingly. The central goal of this dissertation is to build a framework for intelligent notifications that relies on the awareness of users' context and preferences. More specifically, we firstly investigate the impact of physical and cognitive contextual features on users' attentiveness and receptivity to notifications. Secondly, we construct and evaluate a series of models for predicting opportune moments to deliver notifications and mining users' notification delivery preferences in different situations. Finally, we design and evaluate a model for anticipating the right device notifications in cross-platform environments.

A large number of approaches have been developed to simplify construction of, and to reduce errors in, data-driven applications. However, these approaches have not been particularly concerned with compile-time type safety. Type mismatch errors between program and the database schema occur quite often during program development, and the techniques used in these approaches often defer error checking on database operations until runtime. In this thesis, we take a different approach from those previously proposed, based on strict type checking at compile time, type inference, higher-order functions, phantom types, object relational mapping, and loosely coupled database interaction. Instead of using external, literal XML file and string type SQL, we embed the mapping meta data and user defined queries directly in the program, the type safety of which is guaranteed by the program compiler. Such a result is achieved by introducing additional database schema information and using type avatars, a dummy structure used to extend the type checking to embedded queries, during compilation. We show that this approach is practical and effective by implementing a compile-time type-safe object relational framework, called Qanat, in the OCaml programming language and using a loosely coupled SQL database. We further report experimental results obtained by running a number of benchmark tests, and compare the resulting Qanat applications with the equivalent, raw database driver based applications.

Every day environments contain a great variety of deformable objects and it is not possible to program a robot in advance to know about their characteristic behaviours. For this reason, robots have been highly successful in manoeuvring deformable objects mainly in the industrial sector, where the types of interactions are predictable and highly restricted, but research in everyday environments remains largely unexplored. The contributions of this thesis are: i) the application of an elastic/plastic mass-spring method to model and predict the behaviour of deformable objects manipulated by a robot; ii) the automatic calibration of the parameters of the model, using images of real objects as ground truth; iii) the use of piece-wise regression curves to predict the reaction forces, and iv) the use of the output of this force prediction model as input for the mass-spring model which in turn predicts object deformations; v) the use of the obtained models to solve a material classification problem, where the robot must recognise a material based on interaction with it.

External, tree-based, multidimensional access methods typically attempt to provide B+ tree like behaviour and performance in the organisation of large collections of multidimensional data. The B+ tree’s efficiency comes directly from the fact that it organises data occupying a single dimension, which can be linearly ordered, and partitioned at arbitrary points in that order. Using a multiway tree to partition a multidimensional space becomes increasingly difficult with increasing dimensionality, often leading to the loss of desirable properties like high fanout and low internode overlap. The K-D-B tree is an example of a structure in which one property, that of zero internode overlap, is provided at the expense of another, high fanout. Its approach to doing this, by forced splitting, is shared by a collection of other structures, and in 1995 Freeston suggested a novel approach to mitigate the effects of forced splits, by executing them virtually. This approach has not been taken up widely, but we believe it shows a great deal of promise. In the thesis, we examine the virtual forced splitting approach in depth. We identify a number of problems presented by the approach, and propose solutions to them, allowing us to characterise a general class of virtual forced splitting structures that we call VFS-trees. The efficacy of our approach is demonstrated by our implementation of a new VFS structure, and by what we believe to be the first implementation of a BV-tree, together with new algorithms for region and K Nearest Neighbour search. We further report experimental results on construction, exact-match search and K-NN search of BV-trees, and show how they compare, very favourably, with the corresponding operations on the currently most popular multidimensional file access method, the R*-tree.

Multi-agent systems operating in complex domains crucially require agents to interact with each other. An important result of this interaction is that some of the private knowledge of the agents is being shared in the group of agents. This thesis investigates the theme of knowledge sharing from a theoretical point of view by means of the formal tools provided by modal logic. More specifically this thesis addresses the following three points. First, the case of hypercube systems, a special class of interpreted systems as defined by Halpern and colleagues, is analysed in full detail. It is here proven that the logic S5WDn constitutes a sound and complete axiomatisation for hypercube systems. This logic, an extension of the modal system S5n commonly used to represent knowledge of a multi-agent system, regulates how knowledge is being shared among agents modelled by hypercube systems. The logic S5WDn is proven to be decidable. Hypercube systems are proven to be synchronous agents with perfect recall that communicate only by broadcasting, in separate work jointly with Ron van der Meyden not fully reported in this thesis. Second, it is argued that a full spectrum of degrees of knowledge sharing can be present in any multi-agent system, with no sharing and full sharing at the extremes. This theme is investigated axiomatically and a range of logics representing a particular class of knowledge sharing between two agents is presented. All the logics but two in this spectrum are proven complete by standard canonicity proofs. We conjecture that these two remaining logics are not canonical and it is an open problem whether or not they are complete. Third, following a influential position paper by Halpern and Moses, the idea of refining and checking of knowledge structures in multi-agent systems is investigated. It is shown that, Kripke models, the standard semantic tools for this analysis are not adequate and an alternative notion, Kripke trees, is put forward. An algorithm for refining and checking Kripke trees is presented and its major properties investigated. The algorithm succeeds in solving the famous muddy-children puzzle, in which agents communicate and reason about each other's knowledge. The thesis concludes by discussing the extent to which combining logics, a promising new area in pure logic, can provide a significant boost in research for epistemic and other theories for multi-agent systems.

This thesis develops a new approach to evolving Binary Decision Diagrams, and uses it to study evolvability issues. For reasons that are not yet fully understood, current approaches to artificial evolution fail to exhibit the evolvability so readily exhibited in nature. To be able to apply evolvability to artificial evolution the field must first understand and characterise it; this will then lead to systems which are much more capable than they are currently. An experimental approach is taken. Carefully crafted, controlled experiments elucidate the mechanisms and properties that facilitate evolvability, focusing on the roles and interplay between neutrality, modularity, gradualism, robustness and diversity. Evolvability is found to emerge under gradual evolution as a biased distribution of functionality within the genotype-phenotype map, which serves to direct phenotypic variation. Neutrality facilitates fitness-conserving exploration, completely alleviating local optima. Population diversity, in conjunction with neutrality, is shown to facilitate the evolution of evolvability. The search is robust, scalable, and insensitive to the absence of initial diversity. The thesis concludes that gradual evolution in a search space that is free of local optima by way of neutrality can be a viable alternative to problematic evolution on multi-modal landscapes.

Dependency Parsing is a method that builds dependency trees consisting of binary relations that describe the syntactic role of words in sentences. Recently, dependency parsing has seen large improvements due to deep learning, which enabled richer feature representations and flexible architectures. In this thesis we focus on the application of these methods to Transition-based parsing, which is a faster variant. We explore current architectures and examine ways to improve their representation capabilities and final accuracies. Our first contribution is an improvement on the basic architecture at the heart of many current parsers. We show that using Recurrent Neural Network hidden layers, initialised with pretrained weights from a feed forward network, provides significant accuracy improvements. Second, we examine the best parser architecture. We show that separate classifiers for dependency parsing and labelling, with a shared input layer provides the best accuracy. We also show that a parser and labeller can be successfully trained separately. Finally, we propose Recursive LSTM Trees, which can represent an entire tree as a single dense vector, and achieve competitive accuracy with minimal features. The parsers that we develop in this thesis cover many aspects of this task, and are easy to integrate with current methods.