The problem of time series classification (TSC), where we consider any real-valued ordered data a time series, offers a specific challenge. Unlike traditional classification problems, the ordering of attributes is often crucial for identifying discriminatory features between classes. TSC problems arise across a diverse range of domains, and this variety has meant that no single approach outperforms all others. The general consensus is that the benchmark for TSC is nearest neighbour (NN) classifiers using Euclidean distance or Dynamic Time Warping (DTW). Though conceptually simple, many have reported that NN classifiers are very difficult to beat and new work is often compared to NN classifiers. The majority of approaches have focused on classification in the time domain, typically proposing alternative elastic similarity measures for NN classification. Other work has investigated more specialised approaches, such as building support vector machines on variable intervals and creating tree-based ensembles with summary measures. We wish to answer a specific research question: given a new TSC problem without any prior, specialised knowledge, what is the best way to approach the problem? Our thesis is that the best methodology is to first transform data into alternative representations where discriminatory features are more easily detected, and then build ensemble classifiers on each representation. In support of our thesis, we propose an elastic ensemble classifier that we believe is the first ever to significantly outperform DTW on the widely used UCR datasets. Next, we propose the shapelet-transform, a new data transformation that allows complex classifiers to be coupled with shapelets, which outperforms the original algorithm and is competitive with DTW. Finally, we combine these two works with with heterogeneous ensembles built on autocorrelation and spectral-transformed data to propose a collective of transformation-based ensembles (COTE). The results of COTE are, we believe, the best ever published on the UCR datasets.

The need for animated graphical models of the human face is commonplace in the movies, video games and television industries, appearing in everything from low budget advertisements and free mobile apps, to Hollywood blockbusters costing hundreds of millions of dollars. Generative statistical models of animation attempt to address some of the drawbacks of industry standard practices such as labour intensity and creative inflexibility. This work describes one such method for transforming speech animation curves between different expressive styles. Beginning with the assumption that expressive speech animation is a mix of two components, a high-frequency speech component (the content) and a much lower-frequency expressive component (the style), we use Independent Component Analysis (ICA) to identify and manipulate these components independently of one another. Next we learn how the energy for different speaking styles is distributed in terms of the low-dimensional independent components model. Transforming the speaking style involves projecting new animation curves into the lowdimensional ICA space, redistributing the energy in the independent components, and finally reconstructing the animation curves by inverting the projection. We show that a single ICA model can be used for separating multiple expressive styles into their component parts. Subjective evaluations show that viewers can reliably identify the expressive style generated using our approach, and that they have difficulty in identifying transformed animated expressive speech from the equivalent ground-truth.

Steady and unsteady two-dimensional free surface flows subjected to one or multiple disturbances are considered. Flow configurations involving either a single fluid or two layers of fluid of different but constant densities, are examined. Both the effects of gravity and surface tension are included. Fully nonlinear boundary integral equation techniques based on Cauchy’s integral formula are used to derive integro-differential equations to model the problem. The integro-differential equations are discretised and solved iteratively using Newton’s method. Both forced solitary waves and critical flow solutions, where the flow upstream is subcritical and downstream is supercritical, are obtained. The behaviour of the forced wave is determined by the Froude and Bond numbers and the orientation of the disturbance. When a second disturbance is placed upstream in the pure gravity critical case, trapped waves have been found between the disturbances. However, when surface tension is included, trapped waves are shown only to exist for very small values of the Bond number. Instead, it is shown that the disturbance must be placed downstream in the gravity-capillary case to see trapped waves. The stability of these critical hydraulic fall solutions is examined. It is shown that the hydraulic fall is stable, but the trapped wave solutions are only stable in the pure gravity case. Critical, flexural-gravity flows, where a thin sheet of ice rests on top of the fluid are then considered. The flows in the flexural-gravity and gravity-capillary cases are shown to be similar. These similarities are investigated, and the physical significance of both configurations, examined. When two fluids are considered, the situation is more complex. The rigid lid approximation is assumed, and four types of critical flow are investigated. Trapped wave solutions are found to exist in some cases, depending on the Froude number in the lower layer.

Since their introduction, nominal techniques have been widely applied in computer science to reason about syntax of formal systems involving name-binding operators. The work in this thesis is in the area of “nominal" type theory, or more precisely the study of “nominal" simple types. We take Nominal Equational Logic (NEL), which augments equational logic with freshness judgements, as our starting point to introduce the Nominal Lambda Calculus (NLC), a typed lambda calculus that provides a simple form of name-dependent function types. This is a key feature of NLC, which allows us to encode freshness in a novel way. We establish meta-theoretic properties of NLC and introduce a sound model theoretic semantics. Further, we introduce NLC[A], an extension of NLC that captures name abstraction and concretion, and provide pure NLC[A] with a strongly normalising and confluent βη-reduction system. A property that has not yet been studied for “nominal" typed lambda calculi is completeness of βη-conversion for a nominal analogue of full set-theoretic hierarchies. Aiming towards such a result, we analyse known proof techniques and identify various issues. As an interesting precursor, we introduce full nominal hierarchies and demonstrate that completeness holds for βη-conversion of the ordinary typed lambda calculus. The notion of FM-categories was developed by Ranald Clouston to demonstrate that FM-categories correspond precisely to NEL-theories. We augment FM-categories with equivariant exponentials and show that they soundly model NLC-theories. We then outline why NLC is not complete for such categories, and discuss in detail an approach towards extending NLC which yields a promising framework from which we aim to develop a future (sound and complete) categorical semantics and a categorical type theory correspondence. Moreover, in pursuit of a categorical conservative extension result, we study (enriched/ internal) Yoneda isomorphisms for “nominal" categories and some form of “nominal" gluing.

The first four chapters provide an introduction, background information and a summary of results from some of the relevant literature. In these chapters a proof is provided if the author was unable to find either a proof or the result itself stated in the literature. Chapter 5 focuses on syntactic monoids of languages, it introduces some background material from the literature and then proves some characterisations of monoids based on properties that the full preimage of certain subsets satisfy when considered as a formal language over the generating set. In Chapter 6 we examine some natural properties of formal languages which are necessary conditions for a formal language to be a word problem of a group. We look at which subsets of these conditions are sufficient for a formal language satisfying them to be a word problem. Chapter 7 focuses on decision problems. We generalise a theorem of Hartmanis and Hopcroft and use it to settle the decidability for various language classes of the conditions from Chapter 6. Chapter 8 contains a brief exposition of some related areas. We first characterise the co-word problem for groups and then examine a way of constructing groups by intersecting their word problems. We conclude this chapter by proving some simple results about the context-free subset membership problem for groups. Finally, Chapter 9 contains a brief discussion of possible directions in which one could extend the work in this thesis. The results in chapters 5, 6 and 7 are to be considered original unless stated otherwise. Many of the results in chapter 7 have been published in [24]. Many of the results of chapter 6 have been submitted for publication.

The deluge of intelligent objects that are providing continuous access to data and services on one hand and the demand of developers and consumers to handle these data on the other hand require us to think about new communication paradigms and middleware. Based on requirements collected from scenarios from connected car, social networks, and factory of the future this thesis is developing new concepts for fast data processing for hyper-scale systems. In hyperscale systems, such as in the Internet of Things, one emerging requirement is to process, procure, and provide information with almost zero latency. This thesis is introducing new concepts for a middleware to enable fast communication by limiting information flow with filtering concepts using event policy obligations and combining data processing techniques adopted from complex event processing. Fast data processing has to deal with continuous data streams of events, providing a set of operators to manipulate, aggregate, and correlate data. This processing logic needs to be distributed. Distribution helps us to scale on one hand in terms of numbers of data sources (e.g. phones, cars, sensors) and on the other hand to parallelise processing in terms of grouping and partitions (e.g. regional). In our solution, event policies are injected as close as possible to the place where the data is born to optimise traffic. Filters, aggregations and rules help to process the data accordingly. Finally, communication paradigms or interaction patterns support mediation between classical service based request-response interaction and event-based data exchange. This all together builds a middleware enabling fast data processing for hyper-scale systems.

Ubiquitous computing makes various computing devices available throughout the physical setting. Ubiquitous computing devices are distributed and could be mobile, and interactions among them are concurrent and often depend on the location of the devices. Process calculi are formal models of concurrent and mobile systems. The work in this thesis is inspired by the calculus of Mobile Ambients and other process calculi such as Calculus of Communicating Systems which have proved to be successful in the modelling of mobility, communication and structure of systems. We start by developing operational semantics for the calculus of Mobile Ambients and Push and Pull Ambient Calculus, and prove that the semantics are sound and complete with respect to the corresponding underlying reduction semantics. This thesis proposes a Calculus of Communication and Mobility, denoted by CMCPCA, for the modelling of mobility, communication and context awareness in the setting of ubiquitous computing. CMCPCA is an ambient calculus with the in and out capabilities of Cardelli and Gordon as well the push and pull capabilities of Phillips and Vigliotti. CMCPCA has a new form of global communication similar to that in Milner’s CCS. We define a new notion of behavioural equivalence for our calculus in terms of an observation predicate and action transitions. Thus, we define barbed bisimulation and congruence, and capability barbed bisimulation and congruence. We then prove that capability barbed congruence coincides with barbed congruence. We also include in the calculus a new form of context awareness mechanism that allows ambients to query their current location and surrounding. We then propose reduction semantics and operational semantics for the context awareness primitives, and show that the semantics coincide. Several case studies and a variety of small examples show the expressiveness and usefulness of our calculus.

In this thesis we describe two new systems for reasoning about deductive systems: HybridLF and Canonical HybridLF. HybridLF brings together the Hybrid approach (due to Ambler, Crole and Momigliano [15]) to higher-order abstract syntax (HOAS) in Isabelle/HOL with the logical framework LF, a dependently-typed system for proving theorems about logical systems. Hybrid provides a version of HOAS in the form of the lambda calculus, in which Isabelle functions are automatically converted to a nameless de Bruijn represenation. Hybrid allows untyped expressions to be entered as human-readable functions, which are then translated into the machine-friendly de Bruijn form. HybridLF uses and updates these techniques for variable representation in the context of the dependent type theory LF, providing a version of HOAS in the form of LF. Canonical HybridLF unites the variable representation techniques of Hybrid with Canonical LF, in which all terms are in canonical form and definitional equality is reduced to syntactic equality. We extend the Hybrid approach to HOAS to functions with multiple variables by introducing a family of abstraction functions, and use the Isabelle option type to denote errors instead of including an ERR element in the Canonical HybridLF expression type. In both systems we employ the meta-logic M2 to prove theorems about deductive systems. M2 [28] is a first-order logic in which quantifiers range over the objects and types generated by an LF signature (that encodes a deductive system). As part of the implementation of M2 we explore higher-order unification in LF, adapting existing approaches to work in our setting.

Design pattern detection is useful for a range of software comprehension and maintenance tasks. Tools that rely on static or dynamic analysis alone can produce inaccurate results, especially for patterns that rely on the run-time information. Some tools provide facilities for the developer to refine the results by adding their own knowledge. Currently, however, the ability of tools to accommodate this knowledge is very limited; it can only pertain to the detected patterns and cannot provide additional knowledge about the source code, or about its behaviour. In this thesis, we propose an approach to combine existing pattern detection techniques with a structured feedback mechanism. This enables the developer to refine the detection results by feeding-in additional knowledge about pattern implementations and software behaviour. The motivation is that a limited amount of user input can complement the automated detection process, to produce results that are more accurate. To evaluate the approach we applied it to a selection of openly available software systems. The evaluation was carried in two parts. First, an evaluation case study was carried out to detect pattern instances in the selected systems with the help of the user knowledge. Second, a user study of a broader range of expert users of design patterns was conducted in order to investigate the impact of their knowledge on the detection process, and to see whether it is realistic that the user can identify useful knowledge for the detection process. The evaluation results indicate that the proposed approach can yield a significant improvement in the accuracy whilst requiring a relatively small degree of user input from the developer. Moreover, the results show that expert users can supplement the design pattern detection process with a useful feedback that can enhance the detection of design pattern instances in the source code.

Parallelism has become the principal means of sustaining growth in computational performance but there has been relatively little development in general-purpose computer architectures or programming models that can deal effectively with large amounts of it. A new general-purpose model of parallel computing would enable standardisation between architectures, high-volume production and software that is portable between different machines, now and as they develop with future technology. There is substantial opportunity to support this in emerging areas of embedded computing, where the problems of sensing, interaction and decision making can exploit large amounts of parallelism. This thesis demonstrates the essential aspects of a scalable general-purpose model of parallel computation by proposing a Universal Parallel Architecture (UPA), based on a highly-connected communication network, and a high-level parallel programming language for it called sire that can be compiled using simple techniques. The design of sire combines the essential capabilities of sharedmemory programming with the benefits of message passing to support a range of programming paradigms and to provide powerful capabilities for abstraction to build and compose subroutines and data structures in a distributed context. The design also enables program code to be distributed at run time to reuse memory and for processor allocation to be dealt with during compilation so that the overheads of using distributed parallelism are minimal. To evaluate whether the UPA is practical to build, a high-level implementation model using current technologies is described. It demonstrates that the cost of generality is relatively small; for a system with 4,096 processors, an overall investment of around 25% of the system is required for the communication network. Executing on specific UPA implementations, sire's primitives for parallelism, communication and abstraction incur minimal overheads, demonstrating its close correspondence to the UPA and its scalability. Furthermore, as well as executing highly-parallel programs, the UPA can support sequential programming techniques by emulating large memories, allowing general sequential programs to be executed with a factor of 2 to 3 overhead when compared to contemporary sequential machines.