DSpace Community:
http://hdl.handle.net/2381/445
20150329T03:08:50Z

A circular order on edgecoloured trees and RNA mdiagrams
http://hdl.handle.net/2381/31820
Title: A circular order on edgecoloured trees and RNA mdiagrams
Authors: Marsh, Robert J.; Schroll, Sibylle
Abstract: We study a circular order on labelled, medgecoloured trees with k vertices, and show that the set of such trees with a fixed circular order is in bijection with the set of RNA mdiagrams of degree k, combinatorial objects which can be regarded as RNA secondary structures of a certain kind. We enumerate these sets and show that the set of trees with a fixed circular order can be characterized as an equivalence class for the transitive closure of an operation which, in the case m=3, arises as an induction in the context of interval exchange transformations. © 2013 Elsevier Inc.
Description: 2010 Mathematics Subject Classification: Primary: 05C05, 05A15; Secondary: 37B10
20150309T10:16:25Z

Extensions in Jacobian Algebras and Cluster Categories of Marked Surfaces
http://hdl.handle.net/2381/31819
Title: Extensions in Jacobian Algebras and Cluster Categories of Marked Surfaces
Authors: Canakci, Ilke; Schroll, Sibylle
Abstract: In the context of representation theory of finite dimensional algebras, string algebras have been extensively studied and almost all aspects of their representation theory are wellunderstood. One exception to this is the classification of extensions between indecomposable modules. In this paper we explicitly describe such extensions for a class of string algebras, namely gentle algebras associated to surface triangulations. These algebras arise as Jacobian algebras of unpunctured surfaces. We give bases of their extension spaces and show that the dimensions of these extension spaces are given in terms of crossing arcs in the surface. Our approach is new and consists of interpreting snake graphs as indecomposable modules. To give a complete answer, we need to work in the associated cluster category where we explicitly calculate the middle terms of extensions and give a basis of the extension space. We note that not all extensions in the cluster category give rise to extensions for the Jacobian algebra.
Description: Generalized the results to include selfextensions, Added a new section containing an example, New abstract, Added a new result on snake graphs, Minor corrections, 31 pages, 14 figures. 2000 Mathematics Subject Classification. Primary: 13F60, 16P10, 18G15, 18E30
20150309T10:08:08Z

Trivial Extensions of Gentle Algebras and Brauer Graph Algebras
http://hdl.handle.net/2381/31818
Title: Trivial Extensions of Gentle Algebras and Brauer Graph Algebras
Authors: Schroll, Sibylle
Abstract: We show that two wellstudied classes of tame algebras coincide: namely, the class of symmetric special biserial algebras coincides with the class of Brauer graph algebras. We then explore the connection between gentle algebras and symmetric special biserial algebras by explicitly determining the trivial extension of a gentle algebra by its minimal injective cogenerator. This is a symmetric special biserial algebra and hence a Brauer graph algebra of which we explicitly give the Brauer graph. We further show that a Brauer graph algebra gives rise, via admissible cuts, to many gentle algebras and that the trivial extension of a gentle algebra obtained via an admissible cut is the original Brauer graph algebra. As a consequence we prove that the trivial extension of a Jacobian algebra of an ideal triangulation of a Riemann surface with marked points in the boundary is isomorphic to the Brauer graph algebra with Brauer graph given by the arcs of the triangulation.
Description: Added an example. 2010 Mathematics Subject Classification. Primary 16G10, 16G20; Secondary 16S99, 13F60
20150309T10:05:05Z

The geometry of Brauer graph algebras and cluster mutations
http://hdl.handle.net/2381/31817
Title: The geometry of Brauer graph algebras and cluster mutations
Authors: Marsh, Robert J.; Schroll, Sibylle
Abstract: In this paper we establish a connection between ribbon graphs and Brauer graphs. As
a result, we show that a compact oriented surface with marked points gives rise to a unique Brauer
graph algebra up to derived equivalence. In the case of a disc with marked points we show that a dual
construction in terms of dual graphs exists. The rotation of a diagonal in an mangulation gives rise
to a Whitehead move in the dual graph, and we explicitly construct a tilting complex on the related
Brauer graph algebras reflecting this geometrical move.
Description: MSC
primary, 16G10, 16G20, 16E35; secondary, 13F60, 14J10
20150309T09:51:31Z

A circular order on edgecoloured trees and RNA mdiagrams
http://hdl.handle.net/2381/31816
Title: A circular order on edgecoloured trees and RNA mdiagrams
Authors: Marsh, Robert J.; Schroll, Sibylle
Abstract: We study a circular order on labelled, medgecoloured trees with k vertices, and show that the set of such trees with a fixed circular order is in bijection with the set of RNA mdiagrams of degree k , combinatorial objects which can be regarded as RNA secondary structures of a certain kind. We enumerate these sets and show that the set of trees with a fixed circular order can be characterized as an equivalence class for the transitive closure of an operation which, in the case m=3, arises as an induction in the context of interval exchange transformations.
20150309T09:45:40Z

The Ext algebra of a Brauer graph algebra
http://hdl.handle.net/2381/31815
Title: The Ext algebra of a Brauer graph algebra
Authors: Green, Edward L.; Schroll, Sibylle; Snashall, Nicole; Taillefer, Rachel
Abstract: In this paper we study finite generation of the Ext algebra of a Brauer graph algebra by determining the degrees of the generators. As a consequence we characterize the Brauer graph algebras that are Koszul and those that are K_2.
Description: Minor changes only. 2010 Mathematics Subject Classification. 16G20, 16S37, 16E05, 16E30
20150309T09:37:28Z

Group actions and coverings of Brauer graph algebras
http://hdl.handle.net/2381/31808
Title: Group actions and coverings of Brauer graph algebras
Authors: Green, E. L.; Schroll, Sibylle; Snashall, Nicole
Abstract: We develop a theory of group actions and coverings on Brauer graphs that parallels
the theory of group actions and coverings of algebras. In particular, we show that any Brauer
graph can be covered by a tower of coverings of Brauer graphs such that the topmost covering has
multiplicity function identically one, no loops, and no multiple edges. Furthermore, we classify
the coverings of Brauer graph algebras that are again Brauer graph algebras.
Description: 2010 Mathematics Subject Classification. Primary 05E18, 16G20; Secondary 14E20, 16W50, 58E40
20150306T16:08:02Z

Gaussian process regression with multiple response variables
http://hdl.handle.net/2381/31763
Title: Gaussian process regression with multiple response variables
Authors: Wang, Bo; Chen, Tau
Abstract: Gaussian process regression (GPR) is a Bayesian nonparametric technology that has
gained extensive application in databased modelling of various systems, including
those of interest to chemometrics. However, most GPR implementations model only a
single response variable, due to the difficulty in the formulation of covariance function
for correlated multiple response variables, which describes not only the correlation
between data points, but also the correlation between responses. In the paper we
propose a direct formulation of the covariance function for multiresponse GPR, based
on the idea that its covariance function is assumed to be the “nominal” unioutput
covariance multiplied by the covariances between different outputs. The effectiveness
of the proposed multiresponse GPR method is illustrated through numerical examples
and response surface modelling of a catalytic reaction process.
20150304T15:57:18Z

nFold groupoids, ntypes and ntrack categories
http://hdl.handle.net/2381/31752
Title: nFold groupoids, ntypes and ntrack categories
Authors: Blanc, David; Paoli, Simona
Abstract: For each n ≥ 1, we introduce two new Segaltype models of ntypes
of topological spaces: weakly globular nfold groupoids, and a lax version
of these. We show that any ntype can be represented up to homotopy by
such models via an explicit algebraic fundamental nfold groupoid functor.
We compare these models to Tamsamani’s weak ngroupoids, and extract from
them a model for (k − 1)connected ntypes.
Description: 1991 Mathematics Subject Classification. 55S45; 18G50, 18B40
20150304T11:33:24Z

Minimum Distance Estimation of Milky Way Model Parameters and Related Inference
http://hdl.handle.net/2381/31616
Title: Minimum Distance Estimation of Milky Way Model Parameters and Related Inference
Authors: Banerjee, S.; Bhattacharya, S.; Basu, A.; Bose, S.; Chakrabarty, Dalia; Mukherjee, S.
Abstract: We propose a method to estimate the location of the Sun in the disk of the Milky Way using a
method based on the Hellinger distance and construct confidence sets on our estimate of the unknown
location using a bootstrap based method. Assuming the Galactic disk to be twodimensional, the
sought solar location then reduces to the radial distance separating the Sun from the Galactic center
and the angular separation of the Galactic center to Sun line, from a prefixed line on the disk. On
astronomical scales, the unknown solar location is equivalent to the location of us earthlings who
observe the velocities of a sample of stars in the neighborhood of the Sun. This unknown location
is estimated by undertaking pairwise comparisons of the estimated density of the observed set of
velocities of the sampled stars, with the density estimated using synthetic stellar velocity data
sets generated at chosen locations in the Milky Way disk. The synthetic data sets are generated
at a number of locations that we choose from within a constructed grid, at four different base
astrophysical models of the Galaxy. Thus, we work with one observed stellar velocity data and
four distinct sets of simulated data comprising a number of synthetic velocity data vectors, each
generated at a chosen location. For a given base astrophysical model that gives rise to one such
simulated data set, the chosen location within our constructed grid at which the estimated density of
the generated synthetic data best matches the density of the observed data, is used as an estimate
for the location at which the observed data was realized. In other words, the chosen location
corresponding to the highest match offers an estimate of the solar coordinates in the Milky Way
disk. The “match” between the pair of estimated densities is parameterized by the affinity measure
based on the familiar Hellinger distance. We perform a novel crossvalidation procedure to establish
a desirable “consistency” property of the proposed method.
20150205T14:31:58Z

Inverse Bayesian Estimation of Gravitational Mass Density in Galaxies from Missing Kinematic Data
http://hdl.handle.net/2381/31604
Title: Inverse Bayesian Estimation of Gravitational Mass Density in Galaxies from Missing Kinematic Data
Authors: Chakrabarty, Dalia; Saha, P.
Abstract: In this paper, we focus on a type of inverse problem in which the data are expressed as an unknown function of
the sought and unknown model function (or its discretised representation as a model parameter vector). In particular,
we deal with situations in which training data are not available. Then we cannot model the unknown
functional relationship between data and the unknown model function (or parameter vector) with a Gaussian
Process of appropriate dimensionality. A Bayesian method based on state space modelling is advanced instead.
Within this framework, the likelihood is expressed in terms of the probability density function (pdf) of the state
space variable and the sought model parameter vector is embedded within the domain of this pdf. As the measurable
vector lives only inside an identified subvolume of the system state space, the pdf of the state space variable
is projected onto the space of the measurables, and it is in terms of the projected state space density that the
likelihood is written; the final form of the likelihood is achieved after convolution with the distribution of measurement
errors. Application motivated vague priors are invoked and the posterior probability density of the
model parameter vectors, given the data are computed. Inference is performed by taking posterior samples with
adaptive MCMC. The method is illustrated on synthetic as well as real galactic data.
20150204T17:07:47Z

Bayesian Density Estimation via Multiple Sequential Inversions of 2D Images with Application in Electron Microscopy
http://hdl.handle.net/2381/31575
Title: Bayesian Density Estimation via Multiple Sequential Inversions of 2D Images with Application in Electron Microscopy
Authors: Chakrabarty, Dalia; Rigat, F.; Gabrielyan, N.; Beanland, R.; Paul, S.
Abstract: We present a new Bayesian methodology to learn the unknown material density of
a given sample by inverting its twodimensional images that are taken with a Scanning Electron
Microscope. An image results from a sequence of projections of the convolution of the density
function with the unknown microscopy correction function that we also learn from the data;
thus learning of the unknowns demands multiple inversions. We invoke a novel design of experiment,
involving imaging at multiple values of the parameter that controls the subsurface
depth from which information about the density structure is carried, to result in the image.
Reallife material density functions are characterized by high density contrasts and are highly
discontinuous, implying that they exhibit correlation structures that do not vary smoothly. In
the absence of training data, modeling such correlation structures of real material density functions
is not possible. So we discretize the material sample and treat values of the density function
at chosen locations inside it as independent and distributionfree parameters. Resolution
of the available image dictates the discretization length of the model; three models pertaining
to distinct resolution classes (at μm to nano metre scale lengths) are developed. We develop
priors on the material density, such that these priors adapt to the sparsity inherent in the density
function. The likelihood is defined in terms of the distance between the convolution of the unknown
functions and the image data. The posterior probability density of the unknowns given
the data is expressed using the developed priors on the density and priors on the microscopy
correction function as elicited from the Microscopy literature. We achieve posterior samples
using an adaptive MetropoliswithinGibbs inference scheme. The method is applied to learn
the material density of a 3D sample of a nanostructure, using real image data. Illustrations on
simulated image data of alloy samples are also included
20150204T10:02:57Z

Bayesian Learning of Material Density Function by Multiple Sequential Inversions of 2D Images in Electron Microscopy
http://hdl.handle.net/2381/31574
Title: Bayesian Learning of Material Density Function by Multiple Sequential Inversions of 2D Images in Electron Microscopy
Authors: Chakrabarty, Dalia; Paul, S.
Editors: Polpo de Campos, A; Neto,; Ramos Rifo,; Stern,; Lauretto,
Abstract: We discuss a novel inverse problem in which the data is generated by the sequential contractive projections
of the convolution of two unknown functions, both of which we aim to learn. The method is illustrated
using an application that relates to the multiple inversions of image data recorded with a Scanning Electron
Microscope, with the aim of learning the density of a given material sample and the microscopy correction
function. Given the severe logistical difficulties in this application of taking multiple images at different
viewing angles, a novel imaging experiment is undertaken, resulting in expansion of information. In lieu of
training data, it is noted that the highly discontinuous material density function cannot be modelled using a
Gaussian Process (GP) as the parametrisation of the required nonstationary covariance function of such a
GP cannot be achieved without training data. Consequently, we resort to estimating values of the unknown
functions at chosen locations in their domain–locations at which an image data are available. Image data
across a range of resolutions leads to multiscale models which we use to estimate material densities from the
micrometre to nanometre length scales. We discuss applications of the method in nondestructive learning
of material density using simulated metallurgical image data, as well as perform inhomogeneity detection in
multicomponent composite on nano metre scales, by inverting real image data of a brick of nanoparticles.
20150204T09:51:38Z

Simple Locally Finite Lie Algebras of Diagonal Type
http://hdl.handle.net/2381/31502
Title: Simple Locally Finite Lie Algebras of Diagonal Type
Authors: Baranov, Alexander
Abstract: We discuss various characterizations of simple locally finite Lie algebras of diagonal type over an algebraically closed field of characteristic zero.
20150127T14:38:49Z

On time scale invariance of random walks in confined space.
http://hdl.handle.net/2381/31448
Title: On time scale invariance of random walks in confined space.
Authors: Bearup, Daniel; Petrovskii, Sergei
Abstract: Animal movement is often modelled on an individual level using simulated random walks. In such applications it is preferable that the properties of these random walks remain consistent when the choice of time is changed (time scale invariance). While this property is well understood in unbounded space, it has not been studied in detail for random walks in a confined domain. In this work we undertake an investigation of time scale invariance of the drift and diffusion rates of Brownian random walks subject to one of four simple boundary conditions. We find that time scale invariance is lost when the boundary condition is nonconservative, that is when movement (or individuals) is discarded due to boundary encounters. Where possible analytical results are used to describe the limits of the time scaling process, numerical results are then used to characterise the intermediate behaviour.
20150120T14:49:30Z

Modelling biological invasions : population cycles, waves and time delays
http://hdl.handle.net/2381/31392
Title: Modelling biological invasions : population cycles, waves and time delays
Authors: Jankovic, Masha
Abstract: Biological invasions are rapidly gaining importance due to the everincreasing number
of introduced species. Alongside the plenitude of empirical data on invasive
species there exists an equally broad range of mathematical models that might be
of use in understanding biological invasions.
This thesis aims to address several issues related to modelling invasive species
and provide insight into their dynamics. Part I (Chapter 2) documents a case
study of the gypsy moth, Lymantria dispar, invasion in the US. We propose an
alternative hypothesis to explain the patchiness of gypsy moth spread entailing
the interplay between dispersal, predation or a viral infection and the Allee effect.
Using a reactiondiffusion framework we test the two models (preypredator and
susceptibleinfected) and predict qualitatively similar patterns as are observed in
natural populations. As high density gypsy moth populations cause the most
damage, estimating the spread rate would be of help in any suppression strategy.
Correspondingly, using a diffusive SI model we are able to obtain estimates of the
rate of spread comparable to historical data.
Part II (Chapters 3, 4 and 5) is more methodological in nature, and in a single
species context we examine the effect of an ubiquitous phenomenon influencing
population dynamics time delay. In Chapter 3 we show that contrary to the
general opinion, time delays are not always destabilising, using a delay differential
equation with discrete time delay. The concept of distributed delay is introduced
in Chapter 4 and studied through an integrodifferential model. Both Chapters 3
and 4 focus on temporal dynamics of populations, so we further this consideration
to include spatial effects in Chapter 5. Using two different representations of movement,
we show that the onset of spatiotemporal chaos in the wake of population
fronts is possible in a single species model.
20150108T12:53:35Z

Special functions and generalized functions
http://hdl.handle.net/2381/30544
Title: Special functions and generalized functions
Authors: AlSirehy, Fatma.
Abstract: In 1950, Laurent Schwartz marked a convenient starting point for the theory of generalized functions as a subject in its own right. He developed and unified much of the earlier work by Hadamard, Bochner, Sobolev and others. Since then an enormous literature dealing with both theory and applications has grown up, and the subject has undergone extensive further development. The original Schwartz treatment defined a distribution as a linear continuous functional on a space of test functions.;This thesis can be considered a part of the development going in that direction. It is partly an extension of earlier contributions by Fisher, Kuribayashi, Itano and others.;After introducing the background and basic definitions in Chapter One, we developed some basic results concerning the cosine integral Ci(lambda x) and its associated functions Ci+(lambda x) and Ci(lambdax) as well as the neutrix convolution products of the cosine integral.;Chapter Three is devoted to similar results concerning the sine integral Si(lambdax).;In Chapter Four, we generalize some earlier results by Fisher and Kuribayashi concerning the product of the two dimensions xl+ and xlr+ . Moreover, other results are obtained concerning the neutrix product of xlambdar lnp x and sgn x xlambdar. Other theorems are proved about the matrix product of some other distributions such as xl+ ln x+ and xlr .;Chapter Five contains new results about the composition of distributions. It involves the applications of the neutrix limit to establish such relationships between different distributions.
20141215T10:40:16Z

Ancient Egyptian astronomy : timekeeping and cosmography in the New Kingdom
http://hdl.handle.net/2381/30543
Title: Ancient Egyptian astronomy : timekeeping and cosmography in the New Kingdom
Authors: Symons, Sarah.
Abstract: The first part of this study analyses and discusses astronomical timekeeping methods used in the New Kingdom. Diagonal star clocks are examined first, looking at classification of sources, decan lists, and the updating of the tables over time. The date list in the Osireion at Abydos is discussed, and issues concerning its place in the history of astronomical timekeeping are raised. The final stellar timekeeping method, the Ramesside star clock, is then examined. The conventional interpretation of the observational method behind the tables is challenged by a new theory, and a system of analysing the tables is introduced. The conclusions of the previous sections are then gathered together in a discussion of the development of stellar timekeeping methods.;The small instruments known as shadow clocks, and their later relatives the sloping sundials, are also examined. The established hypothesis that the shadow clock was completed by the addition of a crossbar is challenged and refuted.;The second part of this study is based on New Kingdom representations of the sky. Two major texts and several celestial diagrams are discussed in detail, beginning with the Book of Nut, which describes the motions of the sun and stars. New translations of the vignette and dramatic text are presented and discussed. Portions of the Book of the Day describing the behaviour of the sun and circumpolar group of stars are analysed.;Finally, celestial diagrams dating from the New Kingdom are discussed. Their composition and significance is discussed and the conceptual framework behind the diagrams is recreated. By introducing new theories and analysis methods, and using a modern but sympathetic approach to the original sources, this study attempts to update and extend our knowledge of these areas of ancient astronomy..
20141215T10:40:15Z

Data structures and implementation of an adaptive hp finite element method
http://hdl.handle.net/2381/30541
Title: Data structures and implementation of an adaptive hp finite element method
Authors: Senior, Bill.
Abstract: For a fully adaptive hp finite element programme to be implemented it is necessary to implement nirregular meshes efficiently. This requires a sufficiently flexible data structure to be implemented. Because such flexibility is required, the traditional array based approach cannot be used because of its limited applicability. In this thesis this traditional approach has been replaced by an object orientated design and implementation. This leads to an implementation that can be extended easily and safely to include other problems for which it was not originally designed.;The problems with maintaining continuity on such a diverse variety of meshes and how continuity is maintained are discussed. Then the main structure of the mesh is described in the form of domain, subdomains and elements. These are used in conjunction with constraint mappings to give a conforming approximation even with the most irregular of meshes.;There are several varieties of matrix generated by the method each with its own problems of storage. Sparse matrices, with perhaps more than 95% of zero entries, need to be used along side dense matrices. In this thesis an object oriented matrix library is implemented that enables this variety of matrices to be used.;An hp finite element algorithm is then implemented using the data structures, and is tested on a range of test problems. The method is shown to be effective on these problems.
20141215T10:40:15Z

On finite groups of plocal rank one and a conjecture of Robinson
http://hdl.handle.net/2381/30542
Title: On finite groups of plocal rank one and a conjecture of Robinson
Authors: Eaton, Charles.
Abstract: We use the classification of finite simple groups to verify a conjecture of Robinson for finite groups G where G/Op(G) has trivial intersection Sylow psubgroups. Groups of this type are said to have plocal rank one, and it is hoped that this invariant will eventually form the basis for inductive arguments, providing reductions for the conjecture, or even a proof using the results presented here as a base. A positive outcome for Robinson's conjecture would imply Alperin's weight conjecture.;It is shown that in proving Robinson's conjecture it suffices to demonstrate only that it holds for finite groups in which Op(G) is both cyclic and central.;Part of the proof of the former result is used to complete the verification of Dade's inductive conjecture for the Ree groups of type G2.;.
20141215T10:40:15Z

A special numerical method for solving Hamiltonian eigenproblems
http://hdl.handle.net/2381/30540
Title: A special numerical method for solving Hamiltonian eigenproblems
Authors: Maple, Carsten R.
Abstract: In this thesis we develop and implement a new algorithm for finding the solutions of linear Hamiltonian systems arising from ordinary differential equation (ODE) eigenproblems; a large source of these systems is SturmLiouville problems, and these will provide the angle of approach. The convergence properties of the algorithm will be analysed, as will the performance of the algorithm for large values of eigenparameter.;An algorithm is also proposed to find highindex eigenvalues of general SturmLiouville problems.
20141215T10:40:15Z

Anisotropic adaptive refinement for discontinuous galerkin methods
http://hdl.handle.net/2381/30536
Title: Anisotropic adaptive refinement for discontinuous galerkin methods
Authors: Hall, Edward John Cumes
Abstract: We consider both the a priori and a posteriori error analysis and hpadaptation strategies for discontinuous Galerkin interior penalty methods for secondorder partial differential equations with nonnegative characteristic form on anisotropically refined computational meshes with anisotropically enriched polynomial degrees. In particular, we discuss the question of error estimation for linear target functionals, such as the outflow flux and the local average of the solution, exploiting duality based arguments.;The a priori error analysis is carried out in two settings. In the first, full orientation of elements is allowed but only (possibly highorder) isotropic polynomial degrees considered; our analysis, therefore, extends previous results, where only finite element spaces comprising piecewise linear polynomials were considered, by utilizing techniques from tensor analysis. In the second case, anisotropic polynomial degrees are allowed, but the elements are assumed to be axiparallel; we thus apply previously known interpolation error results to the goaloriented setting.;Based on our a posteriori error bound we first design and implement an adaptive anisotropic hrefinement algorithm to ensure reliable and efficient control of the error in the prescribed functional to within a given tolerance. This involves exploiting both local isotropic and anisotropic mesh refinement, chosen on a competitive basis requiring the solution of local problems. The superiority of the proposed algorithm in comparison with a standard hisotropic mesh refinement algorithm and a Hessian based hanisotropic adaptive procedure is illustrated by a series of numerical experiments. We then describe a fully hp adaptive algorithm, once again using a competitive refinement approach, which, numerical experiments reveal, offers considerable improvements over both a standard hpisotropic refinement algorithm and an hanisotropic/pisotropic adaptive procedure.
20141215T10:40:14Z

Multivariate hermite interpolation in euclidean space and its unit sphere by radial basis functions
http://hdl.handle.net/2381/30539
Title: Multivariate hermite interpolation in euclidean space and its unit sphere by radial basis functions
Authors: Luo, Zuhua.
Abstract: In this thesis, we consider radial basis function interpolations in ddimensional Euclidean space Hd and the unit sphere 5d_1, where the data is generated not only by pointevaluations, but also by the derivatives, or differential/pseudodifferential operators. Some sufficient and necessary conditions for the wellposedness of the interpolations are given. The results on sensitivity and sta bility of the interpolation systems are obtained. The optimal properties of the interpolants are analysed through the variational framework and reproducing kernel Hilbert space property, the error bounds and convergence rates of the interpolants are derived. The admissible reproducing kernel Hilbert spaces are also characterised.
20141215T10:40:14Z

On indecomposable modules over clustertilted algebras of type A
http://hdl.handle.net/2381/30538
Title: On indecomposable modules over clustertilted algebras of type A
Authors: Parsons, Mark James
Abstract: Gabriel's Theorem describes the dimension vectors of the finitely generated indecomposable modules over the path algebra of a simplylaced Dynkin quiver. It shows that they can be obtained from the expressions for the positive roots of the corresponding root system in terms of the simple roots. Here, we present a method for finding the dimension vectors of the finitely generated indecomposable modules over a clustertilted algebra of Dynkin type A.;It is known that the quiver of a clustertilted algebra of Dynkin type A is given by an exchange matrix of the corresponding cluster algebra. We define a companion basis for such a quiver to be a Z basis of roots of the integral root lattice of the corresponding root system whose associated matrix of inner products is a positive quasiCartan companion of the corresponding exchange matrix.;Our main result establishes that the dimension vectors of the finitely generated indecomposable modules over a clustertilted algebra of Dynkin type A arise from expressions for the positive roots of the corresponding root system in terms of a companion basis (for the quiver of that algebra). This can be regarded as a generalisation of part of Gabriel's Theorem in the Dynkin type A case. The proof uses the fact that the quivers of the clustertilted algebras of Dynkin type A have a particularly nice description in terms of triangulation of regular polygons.
20141215T10:40:14Z

On the quiver and relations of the Borel Schur algebras
http://hdl.handle.net/2381/30537
Title: On the quiver and relations of the Borel Schur algebras
Authors: Liang, Degang
Abstract: Let K be an infinite field of characteristic p â‰¥ 0 and let n, r be positive integers. Let S+(n, r) be the Borel Schur algebra over K, which is a subalgebra of the Schur algebra S(n, r). We aim to give a description of the Borel Schur algebra S+ (n, r) by finding its quiver and relations. We give a complete description of the quiver and relations for S+(2, r). We also construct a family of embedding from S+(2, r) to S+(n, r + s) which induce embeddings of the corresponding quivers. This gives us some relations for S+(n, r) for n > 2.;We describe the quiver of S+( n, r) for both p = 0 and p > 0. We also describe some relations of special type for p > 0 and find all relations for p = 0.
20141215T10:40:14Z

Uncertainty propagation and reduction in reservoir forecasting
http://hdl.handle.net/2381/30534
Title: Uncertainty propagation and reduction in reservoir forecasting
Authors: Busby, Daniel
Abstract: In this work we focus on nonparametric regression techniques based on Gaussian process, considering both the frequentist and the Bayesian approach. A new sequential experimental design strategy referred to as hierarchical adaptive experimental design is proposed and tested on synthetic functions and on realistic reservoir models using a commercial oil reservoir multiphase flow simulator. Our numerical results show that the method effectively approximate the simulators output with the required approximation accuracy using an affordable number of simulator runs. Moreover, the number of simulations necessary to reach a given approximation accuracy is sensibly reduced respect to other existing experimental designs such as maximin latin hypercubes, or other classical designs used in commercial softwares.;Once an accurate emulator of the simulator output is obtained, it can be also used to calibrate the simulator model using data observed on the real physical system. This process, referred to as history matching in reservoir forecasting, is fundamental to tune input parameters and to consequently reduce output uncertainty. An approach to model calibration using Bayesian inversion is proposed in the last part of this work. Here again a hierarchical emulator is adopted. An innovative sequential design is proposed with the objective of increasing the emulator accuracy around possible history matching solutions. The excellent performances obtained on a very complicated reservoir test case, suggest the high potential of the method to solve complicated inverse problems. The proposed methodology is about to be commercialized in an industrial environment to assist reservoir engineers in uncertainty analysis and history matching.
20141215T10:40:13Z

Euler characteristics and cohomology for quasiperiodic projection patterns
http://hdl.handle.net/2381/30533
Title: Euler characteristics and cohomology for quasiperiodic projection patterns
Authors: Irving, Claire Louise
Abstract: This thesis investigates quasiperiodic patterns and, in particular, polytopal projection patterns, which are produced using the projection method by choosing the acceptance domain to be a polytope. Cohomology theories applicable in this setting are defined, together with the Euler characteristic.;Formulae for the Cech cohomology Hˇ* ( M P ) and Euler characteristic eP are determined for polytopal projection patterns of codimension 2 and calculations are carried out for several examples. The Euler characteristic is shown to be undefined for certain codimension 3 polytopal projection patterns. The Euler characteristic eP is proved to be always defined for a particular class of codimension n polytopal projection patterns P and a formula for eP for such patterns is given. The finiteness or otherwise of the rank of Hˇm(M P ) âŠ— Q for m â‰¥ 0 is also discussed for various classes of polytopal projection patterns. Lastly, a model for M P is considered which leads to an alternative method for computing the rank of Hˇm(M P ) âŠ— Q for P a ddimensional codimension n polytopal projection pattern with d > n..
20141215T10:40:13Z

Efficient method for detection of periodic orbits in chaotic maps and flows
http://hdl.handle.net/2381/30535
Title: Efficient method for detection of periodic orbits in chaotic maps and flows
Authors: Crofts, Jonathan J.
Abstract: An algorithm for detecting unstable periodic orbits in chaotic systems [Phys. Rev. E, 60 (1999), pp. 61726175] which combines the set of stabilising transformations proposed by Schmelcher and Diakonos [Phys. Rev. Lett., 78 (1997), pp. 47334736] with a modified semiimplicit Euler iterative scheme and seeding with periodic orbits of neighbouring periods, has been shown to be highly efficient when applied to lowdimensional system. The difficulty in applying the algorithm to higher dimensional systems is mainly due to the fact that the number of stabilising transformations grows extremely fast with increasing system dimension. in this thesis, we propose to construct stabilising transformations based on the knowledge of the stability matrices of already detected periodic orbits (used as seeds). The advantage of our approach is in a substantial reduction of the number of transformations, which increases the efficiency of the detection algorithm, especially in the case of highdimensional systems. The dependence of the number of transformations on the dimensionality of the unstable manifold rather than on system size enables us to apply, for the first time, the method of stabilising transformations to highdimensional systems. Another important aspect of our treatment of highdimensional flows is that we do not restrict to a Poincare surface of section. This is a particularly nice feature, since the correct placement of such a section in a highdimensional phase space is a challenging problem in itself. The performance of the new approach is illustrated by its application to the fourdimensional kicked double rotor map, a sixdimensional system of three coupled Henon maps and to the KuramotoSivashinsky system in the weakly turbulent regime.
20141215T10:40:13Z

Logic, computation and constraint satisfaction
http://hdl.handle.net/2381/30530
Title: Logic, computation and constraint satisfaction
Authors: Martin, Barnaby D.
Abstract: We study a class of nondeterministic program schemes with while loops: firstly, augmented with a priority queue for memory; secondly, augmented with universal quantification; and, thirdly, augmented with universal quantification and a stack for memory. We try to relate these respective classes of program schemes to wellknown complexity classes and logics.;We study classes of structure on which path system logic coincides with polynomial time P.;We examine the complexity of generalisations of nonuniform boolean constraint satisfaction problems, where the inputs may have a bounded number of quantifier alternations (as opposed to the purely existential quantification of the CSP). We prove, for all boundedalternation prefixes that have some universal quantifiers to the outside of some existential quantifiers (i.e. 2 and above), that this generalisation of boolean CSP respects the same dichotomy as that for the nonuniform boolean quantified constraint satisfaction problem.;We study the nonuniform QCSP, especially on digraghs, through a combinatorial analog  the alternatinghomomorphism problem  that sits in relation to the QCSP exactly as the homomorphism problem sits with the CSP. We establish a trichotomy theorem for the nonuniform QCSP when the template is restricted to antireflexive, undirected graphs with at most one cycle. Specifically, such templates give rise to QCSPs that are either tractable, NPcomplete or Pspacecomplete.;We study closure properties on templates that respect QCSP hardness or QCSP equality. Our investigation leads us to examine the properties of firstorder logic when deprived of the equality relation.;We study the nonuniform QCSP on tournament templates, deriving sufficient conditions for tractablity, NPcompleteness and Pspacecompleteness. In particular, we prove that those tournament templates that give rise to tractable CSP also give rise to tractable QCSP.
20141215T10:40:12Z

Embeddings, fault tolerance and communication strategies in kary ncube interconnection networks
http://hdl.handle.net/2381/30532
Title: Embeddings, fault tolerance and communication strategies in kary ncube interconnection networks
Authors: Ashir, Yaagoub A.
Abstract: The kary ncube interconnection network Qkn, for k 3 and n 2, is ndimensional network with k processors in each dimension. A kary ncube parallel computer consists of kn identical processors, each provided with its own sizeable memory and interconnected with 2n other processors. The kary ncube has some attractive features like symmetry, high level of concurrency and efficiency, regularity and high potential for the parallel execution of various algorithms. It can efficiently simulate other network topologies. The kary ncube has a smaller degree than that of its equivalent hypercube (the one with at least as many nodes) and it has a smaller diameter than its equivalent mesh of processors.;In this thesis, we review some topological properties of the kary ncube Qkn and show how a Hamiltonian cycle can be embedded in Qkn using the Gray codes strategy. We also completely classify when a Qkn contains a cycle of some given length.;The problem of embedding a large cycle in a Qkn with both faulty nodes and faulty links is considered. We describe a technique for embedding a large cycle in a kary ncube Qkn with at most n faults and show how this result can be extended to obtain embeddings of meshes and tori in such a faulty kary ncube.;Embeddings of Hamiltonian cycles in faulty kary ncubes is also studied. We develop a technique for embedding a Hamiltonian cycle in a kary ncube with at most 4n5 faulty links where every node is incident with at least two healthy links. Our result is optimal as there exist kary ncubes with 4n  4 faults (and where every node is incident with at least two healthy links) not containing a Hamiltonian cycle. We show that the same technique can be easily applied to the hypercube. We also show that the general problem of deciding whether a faulty kary ncube contains a Hamiltonian cycle is NPcomplete, for all (fixed) k 3.
20141215T10:40:12Z

On a construction of young modules
http://hdl.handle.net/2381/30531
Title: On a construction of young modules
Authors: Vernon, Marie
Abstract: Let n be a natural number and E an ndimensional vector space over a field K. The symmetric group acts by place permutation on the tensor space E âŠ—r. The Sigmarmodule EâŠ—r can be decomposed into a direct sum of permutation modules Mlambda where lambda is a composition of r into at most n parts.;Each permutation module labelled by such a composition is isomorphic to one labelled be a partition of r into at most n parts, and therefore we assume that lambda is such a partition. The indecomposable direct summands of the permutation module M lambda are called Young modules, and they are labelled by partitions of r into at most n parts.;Throughout this thesis we consider the case where E has dimension two. For lambda a twopart partition of r, we explicitly decompose the module M lambda into a direct sum of Young modules by providing spanning sets for the Young modules.;Moreover, we consider the problem of finding a basis or an algorithm for a basis for the Young modules in this case and, although we have not been able to solve this in general, we give some conjectures and examples showing in which cases we can find a basis.
20141215T10:40:12Z

Selfinjective algebras and the second Hochschild cohomology group
http://hdl.handle.net/2381/30528
Title: Selfinjective algebras and the second Hochschild cohomology group
Authors: AlKadi, Deena
Abstract: In this thesis we study the second Hochschild cohomology group HH 2(Lambda) of a finite dimensional algebra Lambda. In particular, we determine HH2(Lambda) where Lambda is a finite dimensional selfinjective algebra of finite representation type over an algebraically closed field K and show that this group is zero for most such Lambda; we give a basis for HH2(Lambda) in the few cases where it is not zero.;Then we consider algebras of tame representation type; more specifically, we study finite dimensional selfinjective one parametric tame algebras which are not weakly symmetric. Here we show that HH2(Lambda) is nonzero and find a nonzero element eta in HH2(Lambda) and an associative deformation Lambdaeta of Lambda.
20141215T10:40:11Z

Meshfree radical basis function methods for advectiondominated diffusion problems
http://hdl.handle.net/2381/30529
Title: Meshfree radical basis function methods for advectiondominated diffusion problems
Authors: Hunt, David Patrick
Abstract: This thesis is concerned with the numerical solution of advectiondominated diffusion problems. There are essentially two key aspects to this work: the derivatives of an a priori error estimate for a semiLagrangian meshfree method using radial basis function interpolation to numerically approximate the firstorder linear transport problem; and the design and testing of a semiLagrangian meshless method to numerically solve the full parabolic advectiondiffusion problem, using radial basis function Hermite interpolation. We begin by establishing the theory of radical basis function interpolation, including new results for the stability of interpolation via the class of radial basis functions known as polyharmonic splines, as well as error estimates for interpolation by the same class of function. These results provide us with the necessary tools to prove the a priori error estimate for the semiLagrangian advection scheme, given certain assumptions on the smoothness of the solution. We then validate both the scheme and the analysis with a series of numerical experiments. By introducing the concept of Hermite interpolation, we develop and implement a new semiLagrangian method for the numerical approximation of advectiondominated diffusion problems, which is validated through two numerical experiments..
20141215T10:40:11Z

Finiteness conditions on the Extalgebra
http://hdl.handle.net/2381/30527
Title: Finiteness conditions on the Extalgebra
Authors: Davis, Gabriel.
Abstract: Let A be a finitedimensional algebra given by quiver and monomial relations. In [18] we see that the Extalgebra of A is finitely generated only if all the Extalgebras of certain cycle algebras overlying A are finitely generated. Here a cycle algebra Lambda is a finitedimensional algebra given by quiver and monomial relations where the quiver is an oriented cycle. The main result of this thesis gives necessary and sufficient conditions for the Extalgebra of such a Lambda to be finitely generated; this is achieved by defining a computable invariant of Lambda, the smotube. We also give necessary and sufficient conditions for the Extalgebra of Lambda to be Noetherian.;Let Lambda be a triangular matrix algebra, defined by algebras T and U and a TUbimodule M. Under certain conditions we show that if the Extalgebras of T and U are right (respectively left) Noetherian rings, then the Extalgebra of Lambda is a right (respectively left) Noetherian ring. An example shows the hypotheses used cannot be improved. We also specialise to the case where Lambda is a onepoint extension: we give a specific presentation of a result that parallels a similar theorem for the more general case above.
20141215T10:40:11Z

Hamilton thermostatting techniques for molecular dynamics simulation
http://hdl.handle.net/2381/30526
Title: Hamilton thermostatting techniques for molecular dynamics simulation
Authors: Sweet, Christopher Richard
Abstract: Molecular dynamics trajectories that sample from a Gibbs, or canonical, distribution can be generated by introducing a modified Hamiltonian with additional degrees of freedom as described by Nose [46]. Although this method has found widespread use in its time reparameterized NoseHoover form, the lack of a Hamiltonian, and the need to 'tune' thermostatting parameters has limited, its use compared to stochastic methods. In addition, since the proof of the correct sampling is based on an ergodic assumption, thermostatting small of stiff systems often does not given the correct distributions unless the NoseHoover chains [43] method is used, which inherits the NoseHoover deficiencies noted above. More recently the introduction of the Hamiltonian NosePoincare method [11], where symplectic integrators can be used for improved long term stability, has renewed interest in the possibility of Hamiltonian methods which can improve dynamical sampling. This class of methods, although applicable to small systems, has applications in large scale systems with complex chemical structure, such as proteinbath and quantumclassical models.;For Nose dynamics, it is often stated that the system is driven to equilibrium through a resonant interaction between the selfoscillation frequency of the thermostat variable and a natural frequency of the underlying system. By the introduction of multiple thermostat Hamiltonian formulations, which are not restricted to chains, it has been possible to clarify this perspective, using harmonic models, and exhibit practical deficiencies of the standard Nosechain approach. This has led to the introduction of two Hamiltonian schemes, the NosePoincare chains method and the Recursive Multiple Thermostat (RMT) method. The RMT method obtains canonical sampling without the stability problems encountered with chains with the advantage that the choice of Nose mass is independent of the underlying system.
20141215T10:40:11Z

Blocks of fat category O
http://hdl.handle.net/2381/30525
Title: Blocks of fat category O
Authors: Fonseca, Andre
Abstract: We generalize the category O of Bernstein, Gelfand and Gelfand to the so called fat category O, On and derive some of its properties. From a Lie theoretic point of view, contains a significant amount of indecomposable representations that do not belong to O (although it fails to add new simple ones) such as the fat Verma modules. These modules have simple top and socle and may be viewed as standard objects once a block decomposition of is obtained and each block is seen to be equivalent to a category of finite dimensional modules over a finite dimensional standardly stratified algebra. We describe the Ringel dual of these algebras (concluding that principal blocks are self dual) and we obtain the character formulae for their tilting modules. Furthermore, a double centralizer property is proved, relating each block with the corresponding fat algebra of coinvariants. As a byproduct we obtain a classification of all blocks of in terms of their representation type. In the process of determining the quiver and relations which characterize the basic algebras associated to each block of On we prove (for root systems of small rank) a formula establishing the dimension of the Ext1 spaces between simple modules. By borrowing from Soergel some results describing the behaviour of the combinatorial functor V, we are able to compute examples.
20141215T10:40:11Z

Constraint satisfaction problems and related logic
http://hdl.handle.net/2381/30524
Title: Constraint satisfaction problems and related logic
Authors: Madelaine, Florent
Abstract: Feder and Vardi have proved that the class captured by a monadic fragment of existential secondorder logic, MMSNP, is computationally equivalent (via randomised reductions) to the class of constraint satisfaction problems (CSP) while the latter is strictly included in the former. I introduce a new class of combinatorial problems, the socalled forbidden patterns problems (FP), that correspond exactly to the logic MMSNP and introduce some novel algebraic tools like the recolouring that allow me to construct a normal form. This leads to a constructive characterisation of the borderline of CSP within FP: a given problem in FP is either given as a problem in CSP or we build counterexamples. I relate this result to a recent and independent work by Tardif and Nesetril which relies heavily on a correspondence between duality and density. I generalise this approach to FP. Finally, I investigate homomorphism problems for unary algebras.
20141215T10:40:10Z

Monads in coalgebra
http://hdl.handle.net/2381/30522
Title: Monads in coalgebra
Authors: Di Marchi, Federico
Abstract: Universal algebra has long been regarded as a fundamental tool in studying semantics of programming languages. Within this paradigm, one can formulate statements regarding the correctness of a program by looking at the interpretations of the code in any model for the language.;While this provides a description of finite computations, other models have to be introduced in order to provide a semantics for recursion and infinite computations in general. This leads to a study of rational and infinite terms. Such terms arise by a dual construction to that of the finite ones. namely, while the latter form an initial algebra, the former are a final coalgebra.;For this reason, it is natural to approach the study of infinite terms by dualising the categorical model of universal algebra. This leads to various different constructions, which are worth of investigation. In this thesis we approach two of them. In one case, we introduce the notions of cosignature, coequation and comodel, in the spirit of the theory of coalgebraic specification. In the second we focus on the properties of monads which can model infinitary computations. Such monads we call guarded, and include, amongst others, the monads of finite terms, infinite terms, rational terms and term graphs. As a byproduct of identifying this notion, we can solve algebraic systems of equation, which are an abstract counterpart to the notion of a recursive program scheme.;Many guarded monads we encounter are obtained by collecting, in an appropriate sense, a suitable family of coagebras. These examples are all instances of a general theorem we present, which tells under which conditions we can define a monad by a colimit operation, and when such comonads are guarded.;The level of abstraction allowed by the use of the categorical formalism allows us to instantiate some of the results in different categories, obtaining a monadic semantics for rational and infinite parallel term rewriting.
20141215T10:40:10Z

Hierarchic modelling of separable elliptic boundary value problems on thin domains
http://hdl.handle.net/2381/30521
Title: Hierarchic modelling of separable elliptic boundary value problems on thin domains
Authors: Arnold, Mark Edward.
Abstract: The dimensional reduction method for solving Laplace's equation on a flat plate, an arch and a spherical shell is investigated, extending previous work on laminated plates by Vogelius and Babuska (1981). Convergence rates for the error in energy are obtained, extending previous results by deriving explicit values for the constant of approximation and its dependence on the thickness of the domain and the model order. The framework for laminated plates is shown to easily extend to other geometries. Numerical results are given which verify the convergence rates in terms of the thickness. Details are given as to how to implement the dimensional reduction technique and in particular, for a spherical shell, a method is given which reduces the problem to that of inverting relatively small matrices.;A posteriori error estimators are given for each of the geometries under consideration. Error estimators are already known for flat plates. It is shown how the estimators for flat plates can be modified for use in the arch case, and for shells, techniques for estimating the discretization error and modelling error are presented. The a posteriori estimators are then used to derive a refinement algorithm for adaptively constructing hierarchic models for representative problems on each of the geometries under consideration.
20141215T10:40:10Z

Normal and characteristic structure in quasigroups and loops
http://hdl.handle.net/2381/30523
Title: Normal and characteristic structure in quasigroups and loops
Authors: Hardcastle, Tim.
Abstract: In this thesis I shall be exploring the normal and characteristic structure of quasigroups and loops. In recent years there has been a revival of interest in the theory of loops and in particular in the relationship between the properties of a loop and the properties of its multiplication group; and several powerful new theorems have emerged which allow the structural properties of a loop to be related to its multiplication group. I shall combine these ideas with tools developed at the beginning of loop theory to produce some interesting new theorems, principally relating the order of a finite multiplication group to the structure of its loop.
20141215T10:40:10Z

Contextsensitive decision problems in groups
http://hdl.handle.net/2381/30517
Title: Contextsensitive decision problems in groups
Authors: Lakin, Steve.
Abstract: The seemingly distinct areas of group theory, formal language theory and complexity theory interact in an important way when one considers decision problems in groups, such as the question of whether a word in the generators of the group represents the identity or not. In general, these problems are known to be undecidable. Much work has been done on the solvability of these problems in certain groups, however less has been done on the resource bounds needed to solve them, in particular with regard to space considerations. The focus of the work presented here is that of groups with (deterministic) contextsensitive decision problems, that is those that have such problems decidable in (deterministic) linear space. A classification of such groups (similarly to the way that the groups with, for example, regular or contextfree word problem, have been classified) seems untenable at present. However, we present a series of interesting results with regard to such groups, with the intentions that this will lead to a better understanding of this area. Amongst these results, we emphasise the difficulty of the conjugacy problem by showing that a group may have unsolvable conjugacy problem, even if it has a subgroup of finite index with contextsensitive conjugacy problem. Our main result eliminates the previouslyconsidered possibility that the groups with contextsensitive word problem could be classified as the set of groups which are subgroups of automatic groups, by constructing a group with contextsensitive word problem which is not a subgroup of an automatic group. We also consider a range of other issues in this area, in an attempt to increase the understanding of the sort of groups under consideration.
20141215T10:40:09Z

Algorithmic problems in mobile computing environments
http://hdl.handle.net/2381/30520
Title: Algorithmic problems in mobile computing environments
Authors: Bruce, Richard James
Abstract: A mobile computer has become a powerful tool. From laptop computers to cellular phones, in the past decade mobile computers have become prevalent in society. In this thesis we shall review and present various algorithms for use with mobile computers; in particular algorithms for mobile ad hoc wireless networks.;Routing problems in ad hoc wireless networks have been one of the most intensely studied areas of research. We shall review various routing algorithms presented by others, verify some of their results, and present our own algorithms for a particular type of routing called fan routing, along with statistical analysis.;The frequency assignment problem has been investigated for many years. We shall investigate two frequency assignment problems for mobile networks. The first uses a limited amount of information to compute an assignment for a host when it is added to a network, where the remainder of the hosts have already been assigned frequencies. We shall present our algorithms and compare them. The second looks at particular graphs, known as outerplanar graphs, and how to use the minimal amount of frequencies for these graphs.;The final area we shall investigate is efficient update strategies for geometric computing with uncertainty. That is, if you know a property of some objects is true; after some time, is this property still true even if the objects have moved? We present a generalised algorithm for verifying any given property and use this generalised algorithm for the maximal points problem.
20141215T10:40:09Z

The complexity of greedy algorithms on ordered graphs
http://hdl.handle.net/2381/30518
Title: The complexity of greedy algorithms on ordered graphs
Authors: Puricella, Antonio.
Abstract: Let p be any fixed polynomial time testable, nontrivial, hereditary property of graphs. Suppose that the vertices of a graph G are not necessarily linearly ordered but partially ordered, where we think of this partial order as a collection of (possibly exponentially many) linear orders in the natural way. In the first part of this thesis, we prove that the problem of deciding whether a lexicographically first maximal (with respect to one of these linear orders) subgraph of G satisfying p, contains a specified vertex is NPcomplete. For some of these properties p we then show that by applying certain restrictions the problem still remains NPcomplete, and show how the problem can be solved in deterministic polynomial time if the restrictions imposed become more severe.;Let H be a fixed undirected graph. An Hcolouring of an undirected graph G is a homomorphism from G to H. In the second part of the thesis, we show that, if the vertices of G are partially ordered then the complexity of deciding whether a given vertex of G is in a lexicographically first maximal Hcolourable subgraph of G is NPcomplete, if H is bipartite, and Sp2complete, if H is nonbipartite. We then show that if the vertices of G are linearly, as opposed to partially, ordered then the complexity of deciding whether a given vertex of G is in the lexicographically first maximal Hcolourable subgraph of G is Pcomplete, if H is bipartite, and DP2complete, if H is nonbipartite.;In the final part of the thesis we show that the results obtained can be paralleled in the setting of graphs where orders are given by degrees of the vertices.
20141215T10:40:09Z

Error estimates for spaces arising from approximation by translates of a basic function
http://hdl.handle.net/2381/30519
Title: Error estimates for spaces arising from approximation by translates of a basic function
Authors: Vail, Michelle Louise.
Abstract: We look at aspects of error analysis for interpolation by translates of a basic function. In particular, we consider ideas of localisation and how they can be used to obtain improved error estimates. We shall consider certain seminorms and associated spaces of functions which arise in the study of such interpolation methods. These seminorms are naturally given in an indirect form, that is in terms of the Fourier Transform of the function rather than the function itself. Thus, they do not lend themselves to localisation. However, work by Levesley and Light [17] rewrites these seminorms in a direct form and thus gives a natural way of defining a local seminorm. Using this form of local seminorm we construct associated local spaces. We develop bounded, linear extension operators for these spaces and demonstrate how such extension operators can be used in developing improved error estimates. Specifically, we obtain improved L2 estimates for these spaces in terms of the spacing of the interpolation points. Finally, we begin a discussion of how this approach to localisation compares with alternatives.
20141215T10:40:09Z

A CSP approach to the analysis of security protocols
http://hdl.handle.net/2381/30516
Title: A CSP approach to the analysis of security protocols
Authors: Hui, Mei Lin.
Abstract: Security protocols involve an exchange of messages in order to achieve a goal such as authentication of a user or secrecy of a session key. Many established protocols have been found to be flawed using protocol analysis techniques. In this thesis we will be extending current CSPbased protocol modelling techniques.;Recent techniques for analyzing security protocols have tended to concentrate upon the small protocols that are typically found in the academic literature. However, there is a huge gulf between these and most large commercial protocols. As a result, existing techniques are difficult to apply directly to these large protocols.;In this thesis we develop the notion of safe simplifying transformations: transformations that have the property of preserving insecurities; the effect of such transformations is that if we can verify the transformed protocol, then we will have verified the original protocol. We identify a number of safe simplifying transformations, and use them in the analysis of two commercial protocols, the CyberCash Main Sequence protocol and SET.;We extend the CSPbased analysis technique to model the property of nonrepudiation and give a formal generalized definition. Our definition of nonrepudiation is tested against our two case studies.;Another property we model is that of key compromise: the reuse of a compromised session key that might lead to an authentication or secrecy attack. We look at how to model the intruder learning the value of a key and then using it in an attack. We apply this technique to our case studies, looking for key compromise attacks using the session keys.
20141215T10:40:08Z

Formal languages and the word problem in groups
http://hdl.handle.net/2381/30514
Title: Formal languages and the word problem in groups
Authors: Parkes, Duncan W.
Abstract: For any group G and generating set X we shall be primarily concerned with three sets of words over X: the word problem, the reduced word problem, and the irreducible word problem. We explain the relationships between these three sets of words and give necessary and sufficient conditions for a language to be the word problem (or the reduced word problem) of a group.;We prove that the groups which have contextfree reduced word problem with respect to some finite monoid generating set are exactly the contextfree groups, thus proving a conjecture of HaringSmith. We also show that, if a group G has finite irreducible word problem with respect to a monoid generating set X, then the reduced word problem of G with respect to X is simple. In addition, we show that the reduced word problem is recursive (or recursively enumerable) precisely when the word problem is recursive.;The irreducible word problem corresponds to the set of words on the left hand side of a special rewriting system which is confluent on the equivalence class containing the identity. We show that the class of groups which have monoid presentations by means of finite special []confluent stringrewriting systems strictly contains the class of plain groups (the groups which are free products of a finitely generated free group and finitely many finite groups), and that any group which has an infinite cyclic central subgroup can be presented by such a stringrewriting system if and only if it is the direct product of an infinite cyclic group and a finite cyclic group.
20141215T10:40:08Z

Perturbations of black holes in EinsteinCartan theory
http://hdl.handle.net/2381/30515
Title: Perturbations of black holes in EinsteinCartan theory
Authors: White, Andrew.
Abstract: Torsion is a property of spacetime which is not incorporated into the standard formulation of general relativity but which appears as a consequence of unification schemes for fundamental forces. It is, therefore, important to understand its physical consequence. This thesis begins with an introduction to a nonpropagating version of torsion theory as an extension to general relativity. The theory can be described in terms of a pair coupled field equations with torsion algebraically linked to elementary particle spin. In order to develop the theory it is necessary to postulate a form for the energymomentum tensor of spinning matter which is not prescribed in the classical domain. The two main candidates that have been proposed for a spinning fluid are considered. Chapter two contains an independent reworking of Zerilli's [1] perturbation calculation of a particle falling into a Schwarzschild black hole. The perturbation equations are found and the resulting wave equations are derived. The special case of a particle falling radially is considered in detail. Chapter three contains new work which employs the method of Zerilli in torsion theory to consider a particle with spin falling radially into a black hole. The changes to the black hole are found for each of the two energymomentum tensors of Chapter one. This enables us to discount one of these as unphysical. The differential equations describing the gravitational radiation released by this system are derived. Finally in Chapter four these equations are solved to find the gravitational radiation from a spinning particle falling radially. These may be significant for observational assessments of torsion theory.
20141215T10:40:08Z

Approximation by tranlates of a radial basis function
http://hdl.handle.net/2381/30513
Title: Approximation by tranlates of a radial basis function
Authors: Hales, Stephen.
Abstract: The aim of this work is to investigate the properties of approximations obtained by translates of radial basis functions. A natural progression in the discussion starts with an iterative refinement scheme using a strictly positive definite inverse multiquadric. Error estimates for this method are greatly simplified if the inverse multiquadric is replaced by a strictly conditionally positive definite polyharmonic spline. Such error analysis is conducted in a native space generated by the Fourier transform of the basis function. This space can be restrictive when using very smooth basis functions. Some instances are discussed where the native space of can be enlarged by creating a strictly positive definite basis function with comparable approximating properties to , but with a significantly different Fourier transform to . Before such a construction is possible however, strictly positive definite functions in d for d < with compact support must be examined in some detail. It is demonstrated that the dimension in which a function is positive definite can be determined from its univariate Fourier transform.;This work is biased towards the computational aspects of interpolation, and the theory is always given with a view to explaining observable phenomena.
20141215T10:40:08Z

Mixed hp  finite element methods for viscous incompressible fluid flow
http://hdl.handle.net/2381/30511
Title: Mixed hp  finite element methods for viscous incompressible fluid flow
Authors: Coggins, Patrick.
Abstract: The efficient numerical approximation of viscous, incompressible flow by families of mixed finite elements is subject to the satisfaction of a stability or infsup condition between the velocity and pressure approximation spaces.;The present work analyses the stability of mixed hpfinite elements for planar Stokes flow on affine quadrilateral meshes comprising of regular and anisotropic elements. Firstly, a new family of mixed hpfinite elements is presented for regular elements with an infsup constant bounded below independently of the mesh size h and the spectral order p. In particular, the element allows continuous piecewise polynomial pressures to be used.;Next, the stability of families of mixed hpfinite elements on geometrically refined anisotropic elements is considered using a macroelement technique. New results are presented for edge and corner macroelements, in particular, for the latter case, the dependence of the infsup constant on the geometric refinement parameter is explicitly characterised.;The families are then used in the numerical approximation of two physical NavierStokes problems.
20141215T10:40:07Z

Expressibility and tractability
http://hdl.handle.net/2381/30512
Title: Expressibility and tractability
Authors: Gault, Richard.
Abstract: This thesis is composed of three separate, yet related strands. They have in common the notion that computational problems are regarded not as sets of strings, but as classes of finite structures. Our "computing devices", be they of a logical, traditionally computational, or algebraic nature, all work directly upon such structures. This is in contrast to traditional computability and complexity theory, where machines act instead upon some encoding of structures.;We begin by investigating a restriction of the question of whether or not NP = coNP. In particular, we consider the effect of adding a transitive closure operator to monadic NP, and show that the resulting logic is a strict extension of it which is not closed under complementation. This extends Fagin's result that monadic NP is itself not closed under complementation.;We then investigate the expressive power of a class of program schemes which we call RFDPS. We prove a strong result limiting the expressive power of this class, and use it to obtain a strict, infinite hierarchy of problem classes within RFDPS. To our knowledge, this is the first strict, infinite hierarchy in a polynomialtime logic which properly extends inductive fixedpoint logic (with the property that the union of the classes of the hierarchy consists of the class of problems definable in the polynomialtime logic itself).;Finally, we turn our attention to constraint satisfaction problems. This important class of problems is NPhard in general, but many restrictions to it have been identified over the years which ensure its tractability. We introduce a method of combining two tractable classes over disjoint domains, so as to synthesise new tractable classes. We demonstrate that these new classes are genuinely novel, and extend naturally to yet further tractable classes. The algorithms for solving these extended classes can be less than obvious.
20141215T10:40:07Z