This thesis investigates the classification of the behaviour of multiple persons when viewed from a video camera. Work upon a constrained case of multiple person interaction in the form of team games is investigated. A comparison between attempting to model individual features using a (hierarchical dynamic model) and modelling the team as a whole (using a support vector machine) is given. It is shown that for team games such as handball it is preferable to model the whole team. In such instances correct classification performance of over 80% are attained. A more general case of interaction is then considered. Classification of interacting people in a surveillance situation over several datasets is then investigated. We introduce a new feature set and compare several methods with the previous best published method (Oliver 2000) and demonstrate an improvement in performance. Classification rates of over 95% on real video data sequences are demonstrated. An investigation into how the length of time a sequence is observed is then performed. This results in an improved classifier (of over 2%) which uses a class dependent window size. The question of detecting pre/post and actual fighting situations is then addressed. A hierarchical AdaBoost classifier is used to demonstrate the ability to classify such situations. It is demonstrated that such an approach can classify 91% of fighting situations correctly.

While relational databases are still the preferred approach for storing data, XML is emerging as the primary standard for representing and exchanging data. Consequently, it has been increasingly important to provide a uniform XML interface to various data sources— integration; and critical to protect sensitive and confidential information in XML data — access control. Moreover, it is preferable to first detect and repair the inconsistencies in the data to avoid the propagation of errors to other data processing steps. In response to these challenges, this thesis presents an integrated framework for cleaning, integrating and securing data. The framework contains three parts. First, the data cleaning sub-framework makes use of a new class of constraints specially designed for improving data quality, referred to as conditional functional dependencies (CFDs), to detect and remove inconsistencies in relational data. Both batch and incremental techniques are developed for detecting CFD violations by SQL efficiently and repairing them based on a cost model. The cleaned relational data, together with other non-XML data, is then converted to XML format by using widely deployed XML publishing facilities. Second, the data integration sub-framework uses a novel formalism, XML integration grammars (XIGs), to integrate multi-source XML data which is either native or published from traditional databases. XIGs automatically support conformance to a target DTD, and allow one to build a large, complex integration via composition of component XIGs. To efficiently materialize the integrated data, algorithms are developed for merging XML queries in XIGs and for scheduling them. Third, to protect sensitive information in the integrated XML data, the data security sub-framework allows users to access the data only through authorized views. User queries posed on these views need to be rewritten into equivalent queries on the underlying document to avoid the prohibitive cost of materializing and maintaining large number of views. Two algorithms are proposed to support virtual XML views: a rewriting algorithm that characterizes the rewritten queries as a new form of automata and an evaluation algorithm to execute the automata-represented queries. They allow the security sub-framework to answer queries on views in linear time. Using both relational and XML technologies, this framework provides a uniform approach to clean, integrate and secure data. The algorithms and techniques in the framework have been implemented and the experimental study verifies their effectiveness and efficiency.

This thesis addresses the cognitive basis of syntactic adaptation, which biases speakers to repeat their own syntactic constructions and those of their conversational partners. I address two types of syntactic adaptation: short-term priming and longterm adaptation. I develop two metrics for syntactic adaptation within a speaker and between speakers in dialogue: one for short-term priming effects that decay quickly, and one for long-term adaptation over the course of a dialogue. Both methods estimate adaptation in large datasets consisting of transcribed human-human dialogue annotated with syntactic information. Two such corpora in English are used: Switchboard, a collection of spontaneous phone conversation, and HCRC Map Task, a set of task-oriented dialogues in which participants describe routes on a map to one another. I find both priming and long-term adaptation in both corpora, confirming well-known experimental results (e.g., Bock, 1986b). I extend prior work by showing that syntactic priming effects not only apply to selected syntactic constructions that are alternative realizations of the same semantics, but still hold when a broad variety of syntactic phrase structure rules are considered. Each rule represents a cognitive decision during syntactic processing. I show that the priming effect for a rule is inversely proportional to its frequency. With this methodology, I test predictions of the Interactive Alignment Model (IAM, Pickering and Garrod, 2004). The IAM claims that linguistic and situation model agreement between interlocutors in dialogue is the result of a cascade of resource-free, mechanistic priming effects on various linguistic levels. I examine task-oriented dialogue in Map Task, which provides a measure of task success through the deviance of the communicated routes on the maps. I find that long term syntactic adaptation predicts communicative success, and it does so earlier than lexical adaptation. The result is applied in a machine-learning based model that estimates task success based on the dialogue, capturing 14 percent of the variance in Map Task. Short-term syntactic priming differs qualitatively from long term adaptation, as it does not predict task success, providing evidence against learning as a single cognitive basis of adaptation effects. I obtain further evidence for the correlation between semantic activity and syntactic priming through a comparison of the Map Task and Switchboard corpora, showing that short-term priming is stronger in task-oriented dialogue than in spontaneous conversation. This difference is evident for priming between and within speakers, which suggests that priming is a mechanistic rather than strategic effect. I turn to an investigation of the level at which syntactic priming influences language production. I establish that the effect applies to structural syntactic decisions as opposed to all surface sequences of lexical categories. To do so, I identify pairs of part-of-speech categories which consistently cross constituent boundaries defined by the phrase structure analyses of the sentences. I show that such distituents are less sensitive to priming than pairs occurring within constituents. Thus, syntactic priming is sensitive to syntactic structure. The notion of constituent structure differs among syntactic models. Combinatory Categorial Grammar (CCG, Steedman, 2000) formalizes flexible constituent structure, accounting a varying degree of incrementality in syntactic sentence planning. I examine whether priming effects can support the predictions of CCG using the Switchboard corpus, which has been annotated with CCG syntax. I confirm the syntactic priming effect for lexical and non-lexical CCG categories, which encode partially satisfied subcategorization frames. I then show that both incremental and normal-form constituent structures exhibit priming, arguing for language production accounts that support flexible incrementality. The empirical results are reflected in a cognitive model of syntactic realization in language production. The model assumes that language production is subject to the same principles and constraints as any other form of cognition and follows the ACT-R framework (Anderson et al., 2004). Its syntactic process implements my empirical results on priming and is based on CCG. Syntactic planning can take place incrementally and non-incrementally. The model is able to generate simple sentences that vary syntactically, similar to the materials used in the experimental priming literature. Syntactic adaptation emerges due to a preferential and sped-up memory retrieval of syntactic categories describing linearization and subcategorization requirements. Long-term adaptation is explained as a form of learning, while shortterm priming is the result of a combination of learning and spreading activation from semantic and lexical material. Simulations show that the model produces the adaptation effects and their inverse frequency interaction, as well as cumulativity of long-term adaptation.

It has been suggested that theoretical computer science (TCS) suffers more than average from a lack of intrinsic motivation. The reasons provided in the literature include the difficulty of the subject, lack of relevance to the informatics degree or future careers, and lack of enjoyment of the learning experience. This thesis presents evidence of these claims derived from the results of an expert survey. Increasing the students’ perceived control of the learning experience has been shown to increase student motivation in numerous different settings. A few of those also showed increased student performance. This thesis proposes that game-building can be such a setting for the area of TCS. Within the area of TCS, the focus will be on the modelling skills (finite state automata, push-down automata, Turing machines, CCS, etc.) since they form the majority of the curriculum at undergraduate level. It will be demonstrated how arbitrary TCS modelling skills can be mapped onto a game-building framework and allow the students to learn about the former by using the latter. It is hypothesized that the success of the approach depends on the amount of control given to the student. To test this claim, two experimental conditions were used in a repeated-measures design: (1) own-game and (2) pre-defined game. In the former, students are asked to write a game of their own, whereas in the latter, they are asked to copy a pre-defined game. A large demand for the own-game context was observed and results of its effect on performance and enjoyment are presented. Although no main effect of the owngame condition versus the pre-defined game condition was found in terms of either enjoyment or performance, some interesting interaction effects between condition and motivational type were unveiled.

This thesis presents an investigation into the structure of proof in non-standard analysis using proof-planning. The theory of non-standard analysis, developed by Robinson in the 1960s, offers a more algebraic way of looking at proof in analysis. Proof-planning is a technique for reasoning about proof at the meta-level. In this thesis, we use it to encapsulate the patterns of reasoning that occur in non-standard analysis proofs. We first introduce in detail the mathematical theory and the proof-planning architecture. We then present our research methodology, describe the formal framework, which includes an axiomatisation, and develop suitable evaluation criteria. We then present our development of proof-plans for theorems involving limits, continuity and differentiation. We then explain how proof-planning applies to theorems which combine induction and non-standard analysis. Finally we give a detailed evaluation of the results obtained by combining the two attractive approaches of proof-planning and non-standard analysis, and draw conclusions from the work.

Super-/substring problems and super-/subsequence problems are well-known problems in stringology that have applications in a variety of areas, such as manufacturing systems design and molecular biology. Here we investigate the complexity of a new type of such problem that forms a combination of a super-/substring and a super-/subsequence problem. Moreover we introduce different types of minimal superstring and maximal substring problems. In particular, we consider the following problems: given a set L of strings and a string S, (i) find a minimal superstring (or maximal substring) of L that is also a supersequence (or a subsequence) of S, (ii) find a minimal supersequence (or maximal subsequence) of L that is also a superstring (or a substring) of S. In addition some non-super-/non-substring and non-super-/non-subsequence variants are studied. We obtain several NP-hardness or even MAX SNP-hardness results and also identify types of “weak minimal” superstrings and “weak maximal” substrings for which (i) is polynomial-time solvable.

Hyperreconfigurable architectures can adapt their reconfiguration abilities during run time and have been proposed to increase the speed of dynamic reconfiguration. They use two types of dynamic reconfiguration steps. In hyperreconfiguration steps they change their ability for reconfiguration and in ordinary reconfiguration steps they reconfigure the actual contexts for a computation within the limits that have been set by the last hyperreconfiguration step. We study the concept of partial hyperreconfiguration for multi tasks environments. We propose several models for partially hyperreconfigurable architectures and study corresponding reconfiguration problems to find optimal (hyper)reconfigurations. While under a general cost model the problem to find optimal (hyper)reconfigurations is known to be NP-complete even for a single task. We identify an interesting special case that can be solved by a polynomial time algorithm even for multiple tasks. We illustrate the introduced concepts with a partially hyperreconfigurable example architecture and describe the results of simulated runs with a small test application.

Dynamically reconfigurable architectures or systems are able to reconfigure their function and/or structure to suit changing needs of a computation during run time. The increasing flexibility of modern dynamically reconfigurable systems improves their adaptability but also makes fast reconfiguration difficult because of the large amount of necessary reconfiguration information. However, even when a computation uses this flexibility it will not use it all the time. Therefore, we propose to make the potential for reconfigurationitself reconfigurable. This allows for speeding up reconfiguration operations during phases where only parts of the total flexibility are required. Such architectures are called hyperreconfigurable and use two types of reconfiguration operations: hyperreconfigurations for changing the reconfiguration potential and ordinary reconfigurations for actually configuring a new context for a computation.

Dynamically reconfigurable architectures or systems are able to reconfigure their function and/or structure to suit changing needs of a computation during run time. The increasing flexibility of modern dynamically reconfigurable systems improves their adaptability but also makes fast reconfiguration difficult because of the large amount of necessary reconfiguration information. However, even when a computation uses this flexibility it is not use it all the time. Therefore, we propose to make the potential for reconfiguration itself reconfigurable. This allows for speeding up reconfiguration operations during phases where only parts of the total flexibility are required. Such architectures are called hyperreconfigurable and uses two types of reconfiguration operations: hyperreconfigurations for changing the reconfiguration potential and ordinary reconfigurations for actually configuring a new context for a computation.

Hyperreconfigurable architectures adapt their reconfiguration abilities during run time in order to achieve fast dynamic reconfiguration. Models for such architectures have been proposed that change their ability for reconfiguration during hyperreconfiguration steps and in ordinary reconfiguration steps reconfigure the actual contexts for a computation within the limits that have been set by the last hyperreconfiguration step. In this paper we study algorithmic aspects of how to optimally decide what hyperreconfiguration steps should be done during a computation in order to minimize the total time necessary for hyperreconfiguration and ordinary reconfiguration. It is shown that the general problem is NP-hard but fast polynomial time algorithms are given to solve this problem on different types of hyperreconfigurable architectures. These include newly introduced architectures that use a cache to store hypercontexts. We define an example hyperreconfigurable architecture and illustrate the introduced concepts for three application problems.