Coalition formation is a process whereby agents recognise that cooperation with others can occur in a mutually beneficial manner and therefore the agents can choose appropriate temporary groups (named coalitions) to form. The benefit of each coalition can be measured by: the goals it achieves; the tasks it completes; or the utility it gains. Determining the set of coalitions that should form is difficult even in centralised cooperative circumstances due to: (a) the exponential number of different possible coalitions; (b) the ``super exponential'' number of possible sets of coalitions; and (c) the many ways in which the agents of a coalition can agree to distribute its gains between its members (if this gain can be transferred between the agents). The inherent distributed and potentially self-interested nature of multi-agent systems further complicates the coalition formation process. How to design decentralised coalition formation methods for multi-agent systems is a significant challenge and is the topic of this thesis. The desirable characteristics for these methods to have are (among others): (i) a balanced computational load between the agents; (ii) an optimal solution found with distributed knowledge; (iii) bounded communication costs; and (iv) to allow coalitions to form even when the agents disagree on their values. The coalition formation methods presented in this thesis implement one or more of these desirable characteristics. The contribution of this thesis begins with a decentralised dialogue game that utilise argumentation to allow agents to reason over and come to a conclusion on what are the best coalitions to form, when the coalitions are valued qualitatively. Next, the thesis details two decentralised algorithms that allow the agents to complete the coalition formation process in a specific coalition formation model, named characteristic function games. The first algorithm allows the coalition value calculations to be distributed between the agents of the system in an approximately equal manner using no communication, where each agent assigned to calculate the value of a coalition is included in that coalition as a member. The second algorithm allows the agents to find one of the most stable coalition formation solutions, even though each agent has only partial knowledge of the system. The final contribution of this thesis is a new coalition formation model, which allows the agents to find the expected payoff maximising coalitions to form, when each agent may disagree on the quantitative value of each coalition. This new model introduces more risk to agents valuing a coalition higher than the other agents, and so encourages pessimistic valuations.

This thesis presents practical suggestions towards the implementation of the hyperset approach to semi-structured databases and the associated query language Delta. This work can be characterised as part of a top-down approach to semi-structured databases, from theory to practice. The main original part of this work consisted in implementation of the hyperset Delta query language to semi-structured databases, including worked example queries. In fact, the goal was to demonstrate the practical details of this approach and language. The required development of an extended, practical version of the language based on the existing theoretical version, and the corresponding operational semantics. Here we present detailed description of the most essential steps of the implementation. Another crucial problem for this approach was to demonstrate how to deal in reality with the concept of the equality relation between (hyper)sets, which is computationally realised by the bisimulation relation. In fact, this expensive procedure, especially in the case of distributed semi-structured data, required some additional theoretical considerations and practical suggestions for efficient implementation. To this end the 'local/global' strategy for computing the bisimulation relation over distributed semi-structured data was developed and its efficiency was experimentally confirmed. Finally, the XML-WDB format for representing any distributed WDB as system of set equations was developed so that arbitrary XML elements can participate and, hence, queried by the -language. The query system with the syntax of the language and several example queries from this thesis is available online at http://www.csc.liv.ac.uk/˜molyneux/t/

This thesis defines the Broadcasting Automata model as an intuitive and complete method of distributed pattern formation, partitioning and distributed geometric computation. The system is examined within the context of Swarm Robotics whereby large numbers of minimally complex robots may be deployed in a variety of circumstances and settings with goals as diverse as from toxic spill containment to geological survey. Accomplishing these tasks with such simplistic machines is complex and has been deconstructed in to sub-problems considered to be signif- icant because, when composed, they are able to solve much more complex tasks. Sub-problems have been identified, and studied as pattern formation, leader elec- tion, aggregation, chain formation, hole avoidance, foraging, path formation, etc. The Broadcasting Automata draws inspiration from a variety of sources such as Ad-Hoc radio networks, cellular automata, neighbourhood sequences and nature, employing many of the same pattern forming methods that can be seen in the superposition of waves and resonance. To this end the thesis gives an in depth analysis of the primitive tools of the Broadcasting Automata model, nodal patterns, where waves from a variety of transmitters can in linear time construct partitions and patterns with results per- taining to the numbers of different patterns and partitions, along with the number of those that differ, are given. Using these primitives of the model a variety of algorithms are given including leader election, through the location of the centre of a discrete disc, and a solution to the Firing Squad Synchronisation problem. These problems are solved linearly.An exploration of the ability to vary the broadcasting radius of each node leads to results of categorisations of digital discs, their form, composition, encodings and generation. Results pertaining to the nodal patterns generated by arbitrary transmission radii on the plane are explored with a connection to broadcasting sequences and approximation of discrete metrics of which results are given for the approximation of astroids, a previously unachievable concave metric, through a novel application of the aggregation of waves via a number of explored functions. Broadcasting Automata aims to place itself as a robust and complete linear time and large scale system for the construction of patterns, partitions and geometric computation. Algorithms and methodologies are given for the solution of problems within Swarm Robotics and an extension to neighbourhood sequences. It is also hoped that it opens up a new area of research that can expand many older and more mature works.

This thesis studies the computational complexity of approximately evaluating partition functions. For various classes of partition functions, we investigate whether there is an FPRAS: a fully polynomial randomised approximation scheme. In many of these settings we also study 'expressibility', a simple notion of defining a constraint by combining other constraints, and we show that the results cannot be extended by expressibility reductions alone. The main contributions are: • We show that there is no FPRAS for evaluating the partition function of the hard-core gas model on planar graphs at fugacity 312, unless RP = NP. • We generalise an argument of Jerrum and Sinclair to give FPRASes for a large class of degree-two Boolean #CSPs. • We initiate the classification of degree-two Boolean #CSPs where the constraint language consists of a single arity 3 relation. • We show that the complexity of approximately counting downsets in directed acyclic graphs is not affected by restricting to graphs of maximum degree three. • We classify the complexity of degree-two #CSPs with Boolean relations and weights on variables. • We classify the complexity of the problem #CSP(F) for arbitrary finite domains when enough non-negative-valued arity 1 functions are in the constraint language. • We show that not all log-supermodular functions can be expressed by binary logsupermodular functions in the context of #CSPs.

This thesis describes research work undertaken in the fields of text and questionnaire mining. More specifically, the research work is directed at the use of text classification techniques for the purpose of summarising the free text part of questionnaires. In this thesis text summarisation is conceived of as a form of text classification in that the classes assigned to text documents can be viewed as an indication (summarisation) of the main ideas of the original free text but in a coherent and reduced form. The reason for considering this type of summary is because summarising unstructured free text, such as that found in questionnaires, is not deemed to be effective using conventional text summarisation techniques. Four approaches are described in the context of the classification summarisation of free text from different sources, focused on the free text part of questionnaires. The first approach considers the use of standard classification techniques for text summarisation and was motivated by the desire to establish a benchmark with which the more specialised summarisation classification techniques presented later in this thesis could be compared. The second approach, called Classifier Generation Using Secondary Data (CGUSD), addresses the case when the available data is not considered sufficient for training purposes (or possibly because no data is available at all). The third approach, called Semi-Automated Rule Summarisation Extraction Tool (SARSET), presents a semi-automated classification technique to support document summarisation classification in which there is more involvement by the domain experts in the classifier generation process, the idea was that this might serve to produce more effective summaries. The fourth is a hierarchical summarisation classification approach which assumes that text summarisation can be achieved using a classification approach whereby several class labels can be associated with documents which then constitute the summarisation. For evaluation purposes three types of text were considered: (i) questionnaire free text, (ii) text from medical abstracts and (iii) text from news stories.

In this thesis, we study the problems of determinisation and complementation of finite automata on infinite words. We focus on two classes of automata that occur naturally: generalised Büchi automata and nondeterministic parity automata. Generalised Büchi and parity automata occur naturally in model-checking, realisability checking and synthesis procedures. We first review a tight determinisation procedure for Büchi automata, which uses a simplification of Safra trees called history trees. As Büchi automata are special types of both generalised Büchi and parity automata, we adjust the data structure to arrive at suitably tight determinisation constructions for both generalised Büchi and parity automata. As the parity condition describes combinations of Büchi and CoBüchi conditions, instead of immediately modifying the data structure to handle parity automata, we arrive at a suitable data structure by first looking at a special case, Rabin automata with one accepting pair. One pair Rabin automata correspond to parity automata with three priorities and serve as a starting point to modify the structures that result from Büchi determinisation: we then nest these structures to reflect the standard parity condition and describe a direct determinisation construction. The generalised Büchi condition is characterised by an accepting family with 'k' accepting sets. It is easy to extend classic determinisation constructions to handle generalised Büchi automata by incorporating the degeneralization algorithm in the determinisation construction. We extend the tight Büchi construction to do exactly this. Our determinisation constructions go to deterministic Rabin automata. It is known that one can determinise to the more convenient parity condition by incorporating the standard Latest Appearance Record construction in the determinisation procedure. We determinise to parity automata using this technique. We prove lower bounds on these constructions. In the case of determinisation to Rabin automata, our constructions are tight to the state. In the case of determinisation to parity, there is a constant factor ≤ 1.5 between upper and lower bounds reducing to optimal(to the state) in the case of Büchi and 1-pair Rabin. We also reconnect tight determinisation and complementation and provide constructions for complementing generalised Büchi and parity automata by starting withour data structure for determinisation. We introduce suitable data structures for the complementation procedures based on the data structure used for determinisation. We prove lower bounds for both constructions that are tight upto an O(n) factor where 'n' is the number of states of the nondeterministic automaton that is complemented.

This thesis proposes new methods and tools for helping human traders to compete in a high-frequency trading environment. Human traders have difficulty trading against predatory algorithms and the thesis proposes methods that support the creation of assistive tools that can help human traders to compete profitably. It also develops further understanding of classical decision-making theory in a realtime trading context demonstrating that human traders improve decision-making biases when linked together in groups or with an assistive machine. As described in the thesis human traders are monitored, and their data is captured, in realtime and in situ. The trading performance and behavioural characteristics of the traders are studied in this context in order to determine if they can be positively modified. The thesis presents a new model for studying human trading behaviour in realtime and in situ using unique software. It also describes the basis for the development of a range of interventionist and assistive tools that are designed to augment trading performance. The approach put forward is unique in its application. It also provides evidence that human traders are willing to allow machines to augment their trading decisions. The contributions of this thesis are that it overcomes the problem of assessing human trader risk-taking behaviour in realtime and in situ, it makes sense of human trading behaviour at realtime speeds and then it shows that, with new approaches to human-machine collaboration, trading performance improves and classic decision-making biases are reduced.

This thesis addresses a problem that faces developers of applications for mobile devices. There is an ever-increasing number of mobile platforms and form factors in the world, and mobile developers have to build applications that can be used on as many of these as possible while still retaining usability. Furthermore, because of constraints put on the development process by the companies that develop the mobile platforms, there is an absolute requirement that the applications produced by the tool conform to the user interface guidelines for each platform. To address this problem, this thesis uses the concept of “case”, which is a phe- nomenon from natural language. In natural languages, case has many functions and plays a part in many systems. This thesis engages with case in one of these functions: it permits flexible word ordering. Case is used here to allow flexible or- dering of elements within the user’s dialogue with the machine. Case may either be useful because of some analogical process in the developer’s head or because of deeper ideas in linguistic theory. To evaluate this idea, a suitable case system was embedded in a tool and this tool was used in three distinct contexts. First, applications were built for three external companies. Second, a workshop study was done with external developers. Third, more external developers were given the tool for a longer period to produce an application of their choosing. These three contexts gave an excellent view into the use of the case system during the development of applications. This evaluation showed that the kinds of functions that case describes are rel- evant to describing user interfaces; that it is possible to implement a plausible case system usefully in a software tool, at least for mobile development; that the case system when embedded within the tool can be used to build useful applications; and that case can be used and understood by developers other than the author.

Context-Aware applications make use of sensed and gathered information about a user’s state to better tailor their behaviour to the user’s needs. There are many streams of information that can be employed as context; these elements have a variety of structures and not all of them are static or fully known to developers at runtime, this can make it challenging to add new streams of context to an application and keep those streams whose structure frequently changes updated. Heterogeneity of sensor technology and information sources means two users may generate information about the same aspect of their state, their location for example, in two different formats. Although there are examples of services that can relate a value from one location sensing technology to a value from another, we lack a general service for building and reasoning about these relationships between any and all representations of context. Moreover, due to their frequent use of sensed physical information, context-aware applications also generate seams, which may cause uncertainty, error and unexpected behaviours. Developers need a simple way to think about context; one which supports the many heterogeneous types of information it comprises, allows them to update the structures of those types as they change or are discovered, gives them the means to reason about relationships between users whose devices sense the same sort of context using different technologies, and which provides them with both opportunity and means to address and respond to some of the seams arising in their applications. This work presents a spatial model for reasoning about context using presence and awareness that attempts to address the requirements above. The model is realised in a platform comprised of an API and a Context-Broker, which provides context-reasoning and relation services for applications that communicate with it via a dataspace. Using the platform to implement a location-aware game raises several issues concerning the usability and presentation of its paradigms and a seam encountered by a user playing the game. We use this as an opportunity to explore methods for analysing how underlying models, platforms and applications create meaning in pervasive and Mixed-Reality context-aware applications, and how seams operate within them. We present changes to our model and platform based on the conclusions drawn from this analysis. Our analysis of the user’s experience leads us to conclude that model paradigms must be carefully structured to support the multiple ways in which context is used, that both spatial and temporal discontinuity can create user confusion and that when mixing virtual and physical spaces it is important to communicate fully all the structures imposed upon them. Our analysis of seams leads us to the conclusion that responses to them can be usefully positioned as simple processes of disparity resolution involving the restructuring of one or more spaces or milieu involved in the application.

This thesis addresses the linguistic phenomenon of vague language (VL) and its effect on the creation of identity in the emerging and developing field of human-agent interaction (HAI). Current research on VL has focused on human interaction, while similar existing literature on language in HAI has focused on politeness theory and facework. This thesis brings the two research fields together and uses them as a focusing lens to investigate the issue of identity in agents – software with varying degrees of autonomy and intelligence. Agents are increasingly common in our everyday lives, particularly in the role of an instructor. Intelligent personal assistants are a frequent feature on smartphones, automated checkout systems pervade supermarkets both large and small, and satellite navigation systems have been a mainstay for over a decade now. Despite their frequency, there is relatively little research into the communication challenges surrounding HAI. Much like other people, the language and voice of agents have the ability to affect our perceptions and of them, and shape the way in which we create their identities. Instruction giving, amongst other facets of talk, in human communication can be mitigated through the use of VL. This can reduce the imposition we have on interaction partners, pay respect to a listener’s face, and establish and maintain a positive rapport with our interlocutors. This can have a profound effect on the desire to interact with someone again. Furthermore, agents that use speech to communicate are assigned one of two varieties of voice – synthesised or pre-recorded human speech, both of which have documented benefits and drawbacks. Given the rise of agents in the modern world, it is in the best interest of all parties to understand the salient variables that affect our perceptions of agents, and what effect VL and other variables such as voice in language and voice may have in our interactions with them. This thesis provides a novel approach to investigating both VL and voice in HAI. A general framework is presented with the use of a specific VL model to apply in the interactions, which is designed around verbal agents giving people instructions on how to construct Lego models. The first study compares the effects of a vague and non-vague verbal agent in this context, while the second study focuses on the comparative use of synthesised text-to-speech voices and professional human recordings in the same context. The results from the investigation reveal key findings regarding the use of VL in a verbal agent instructive context. The first study indicated that a synthesised agent voice is better suited to using non-vague instructions, while the second study revealed that a professional voice actor is a preferable candidate for using VL in comparison to two different synthesised voices. These findings discuss the issue of identities in HAI. They reveal that, when an agent instructor is perceived to have a voice that is non-human and machinelike, it is more likely that its use of VL will be received less positively. This is often because the combination of voice and language do not mix, but is also a result of a clash of perceived group identities between agent and human speech. As agents are typically direct, the use of “humanlike” VL can create a large disparity between a person’s expectations of agent speech and the reality of the interaction. Similarly, if an agent’s voice has more of a humanlike feel to it, then its use of VL will create less disparity and has the potential to bridge the gap between these two group identities. This poses discussions on the nature of agent identity and how it compares to those in humans. The thesis concludes with reflection on the findings in light of existing linguistic theories, and how further research into this field may assist agent designers, researchers, and agent users alike. A suggestion of employing a corpus linguistics approach to HAI is proposed, which may pave the way for future success in this area.