CIRCA Theses
PhD Theses
2012  Nabilah AbuGhazalh 
Finiteness Conditions for Unions of Semigroups  
In this thesis we prove the following:


Available as: PDF  
2011  Neil Moore 
Improving the Efficiency of Learning CSP Solvers  
Backtracking CSP solvers provide a powerful framework for search and reasoning. The aim of constraint learning is increase global reasoning power by learning new constraints to boost reasoning and hopefully reduce search effort. In this thesis constraint learning is developed in several ways to make it faster and more powerful.First, lazy explanation generation is introduced, where explanations are generated as needed rather than continuously during propagation. This technique is shown to be effective is reducing the number of explanations generated substantially and concequently reducing the amount of time taken to complete a search, over a wide selection of benchmarks.Second, a series of experiments are undertaken investigating constraint forgetting, where constraints are discarded to avoid time and space costs associated with learn ing new constraints becoming too large. A major empirical investigation into the overheads introduced by unbounded constraint learning in CSP is conducted. This is the first such study in either CSP or SAT. Two significant results are obtained. The first is that typically a small percentage of learnt constraints do most propagation. While this is conventional wisdom, it has not previously been the subject of empirical study. The second is that even constraints that do no effective propagation can incur significant time overheads. Finally, the use of forgetting techniques from the literature is shown to significantly improve the performance of modern learning CSP solvers, contradicting some previous research.
Finally, learning is generalised to use disjunctions of arbitrary constraints, where before only disjunctions of assignments and disassignments have been used in practice (gnogood learning). The details of the implementation undertaken show that major gains in expressivity are available, and this is confirmed by a proof that it can save an exponential amount of search in practice compared with gnogood learning. Experiments demonstrate the promise of the technique. 

Available as: PDF  
2010  Hannah Coutts 
Topics in Computational Group Theory: Primitive permutation groups and matrix group normalisers  
Part I of this thesis presents methods for finding the primitive permutation groups of degree d, where 2500 ≤ d < 4096, using the O’NanScott Theorem and Aschbacher’s theorem. Tables of the groups G are given for each O’NanScott class. For the nonaffine groups, additional information is given: the degree d of G, the shape of a stabiliser in G of the primitive action, the shape of the normaliser N in S_{d} of G and the rank of N.Part II presents a new algorithm NormaliserGL for computing the normaliser in GL_{n}(q) of a group G ≤ GL_{n}(q). The algorithm is implemented in the computational algebra system Magma and employs Aschbacher’s theorem to break the problem into several cases. The attached CD contains the code for the algorithm as well as several test cases which demonstrate the improvement over MAGMA’s existing algorithm.  
Available as: PDF  
2010  Andreas Distler 
Classification and Enumeration of Finite Semigroups  
The classification of finite semigroups is difficult even for small orders because of their large number. Most finite semigroups are nilpotent of nilpotency rank 3. Formulae for their number up to isomorphism, and up to isomorphism and antiisomorphism of any order are the main results in the theoretical part of this thesis. Further studies concern the classification of nilpotent semigroups by rank, leading to a full classification for large ranks.In the computational part, a method to find and enumerate multiplication tables of semigroups and subclasses is presented. The approach combines the advantages of computer algebra and constraint satisfaction, to allow for an efficient and fast search. The problem of avoiding isomorphic and antiisomorphic semigroups is dealt with by supporting standard methods from constraint satisfaction with structural knowledge about the semigroups under consideration. The approach is adapted to various problems, and realised using the computer algebra system GAP and the constraint solver Minion. New results include the numbers of semigroups of order 9, and of monoids and bands of order 10. Up to isomorphism and antiisomorphism there are 52,989,400,714,478 semigroups with 9 elements, 52,991,253,973,742 monoids with 10 elements, and 7,033,090 bands with 10 elements. That constraint satisfaction can also be utilised for the analysis of algebraic objects is demonstrated by determining the automorphism groups of all semigroups with 9 elements.A classification of the semigroups of orders 1 to 8 is made available as a data library in form of the GAP package Smallsemi. Beyond the semigroups themselves a large amount of precomputed properties is contained in the library. The package as well as the code used to obtain the enumeration results are available on the attached DVD.  
Available as: PDF  
2010  Andrea Rendl 
Effective Compilation of Constraint Models  
Constraint Programming is a powerful technique for solving largescale combinatorial (optimisation) problems. However, it is often inaccessible to users without expert knowledge in the area, precluding the widespread use of Constraint Programming techniques. This thesis addresses this issue in three main contributions.First, we propose a simple ‘modelandsolve’ approach, consisting of a framework where the user formulates a solverindependent problem model, which is then automatically tailored to the input format of a selected constraint solver (a process similar to compiling a highlevel modelling language to machine code). The solver is then executed on the input, solver, and solutions (if they exist) are returned to the user. This allows the user to formulate constraint models without requiring any particular background knowledge of the respective solver and its solving technique. Furthermore, since the framework can target several solvers, the user can explore different types of solvers.Second, we extend the tailoring process with model optimisations that can compensate for a wide selection of poor modelling choices that novices (and experts) in Constraint Programming often make and hence result in redundancies. The elimination of these redundancies by the proposed optimisation techniques can result in solving time speedups of over an order of magnitude, in both naive and expert models. Furthermore, the optimisations are particularly lightweight, adding negligible overhead to the overall translation process.
The third contribution is the implementation of this framework in the tool TAILOR, that currently translates 2 different solverindependent modelling languages to 3 different solver formats and is freely available online. It performs almost all optimisation techniques that are proposed in this thesis and demonstrates its significance in our empirical analysis. In summary, this thesis presents a framework that facilitates modelling for both experts and novices: problems can be formulated in a clear, highlevel fashion, without requiring any particular background knowledge about constraint solvers and their solving techniques, while (sometimes naturally occurring) redundancies in the model are eliminated for practically no additional cost, improving the respective model in solving performance by up to an order of magnitude. 

Available as: PDF  
2009  Yann Péresse 
Generating Uncountable Transformation Semigroups  
We consider naturally occurring, uncountable transformation semigroups S and investigate the following three questions.
Semigroups S for which we answer question (1.) include: the semigroups of the injective functions and the surjective functions on a countably infinite set; the semigroups of the increasing functions, the Lebesgue measurable functions, and the differentiable functions on the closed unit interval [0, 1]; and the endomorphism semigroup of the random graph. We investigate questions (2.) and (3.) in the case where S is the semigroup Ω^{Ω} of all functions on a countably infinite set Ω. Subsets U of Ω^{Ω} under consideration are semigroups of Lipschitz functions on Ω with respect to discrete metrics on Ω and semigroups of endomorphisms of binary relations on Ω such as graphs or preorders. 

Available as: PDF  
2009  Fiona Brunk 
Intersection Problems in Combinatorics  
With the publication of the famous ErdösKoRado Theorem in 1961, intersection problems became a popular area of combinatorics. A family of combinatorial objects is tintersecting if any two of its elements mutually tintersect, where the latter concept needs to be specified separately in each instance. This thesis is split into two parts; the first is concerned with intersecting injections while the second investigates intersecting posets.We classify maximum 1intersecting families of injections from {1, . . . , k} to {1, . . . , n}, a generalisation of the corresponding result on permutations from the early 2000s. Moreover, we obtain classifications in the general t > 1 case for different parameter limits: if n is large in terms of k and t, then the socalled fixfamilies, consisting of all injections which map some fixed set of t points to the same image points, are the only tintersecting injection families of maximal size. By way of contrast, fixing the differences k – t and n – k while increasing k leads to optimal families which are equivalent to one of the socalled saturation families, consisting of all injections fixing at least r + t of the first 2r + t points, where r = ⌊(k – t)/2⌋. Furthermore we demonstrate that, among injection families with tintersecting and leftcompressed fixed point sets, for some value of r the saturation family has maximal size.The concept that two posets intersect if they share a comparison is new. We begin by classifying maximum intersecting families in several isomorphism classes of posets which are linear, or almost linear. Then we study the union of the almost linear classes, and derive a bound for an intersecting family by adapting Katona’s elegant cycle method to posets. The thesis ends with an investigation of the intersection structure of poset classes whose elements are close to the antichain.
The overarching theme of this thesis is fixing versus saturation: we compare the sizes and structures of intersecting families obtained from these two distinct principles in the context of various classes of combinatorial objects. 

Available as: PDF  
2007  Björn Assmann 
Applications of Lie methods to computations with polycyclic groups  
In this thesis we demonstrate the algorithmic usefulness of the socalled Mal’cev correspondence for computations with inï¬nite polycyclic groups. This correspondence between Qpowered nilpotent groups and rational nilpotent Lie algebras was discovered by Anatoly Mal’cev in 1951.We show how the Mal’cev correspondence can be realized on a computer. We explore two possibilities for this purpose and compare them: the first one uses matrix embeddings and the second the BakerCampbellHausdorff formula.Then, we describe a new collection algorithm for polycyclically presented groups, which we call Mal’cev collection. Algorithms for collection lie at the heart of most methods dealing with polycyclically presented groups. The current state of the art is “collection from the left” as recently studied by Gebhardt, LeedhamGreen/Soicher and VaughanLee. Mal’cev collection is in some cases dramatically faster than collection from the left, while using less memory.
Further, we explore how the Mal’cev correspondence can be used to describe symbolically the collection process in polycyclically presented groups. In particular, we describe an algorithm that computes the collection functions for splittable polycyclic groups. This algorithm is based on work by du Sautoy. We apply it to the computation of propcompletions of polycyclic groups. Finally we describe a practical algorithm for testing polycyclicity of finitely generated rational matrix groups. Previously, not only did no such method exist but it was not clear whether this question was decidable at all. Most of the methods described in this thesis are implemented in the computer algebra system GAP and publicly available as part of the GAP packages Guarana and Polenta. Reports on the implementation including runtimes for some examples are given at the appropriate places. 

Available as: PDF  
2007  Peter Nightingale 
Consistency and the Quantified Constraint Satisfaction Problem  
Constraint satisfaction is a very well studied and fundamental artificial intelligence technique. Various forms of knowledge can be represented with constraints, and reasoning techniques from disparate fields can be encapsulated within constraint reasoning algorithms. However, problems involving uncertainty, or which have an adversarial nature (for example, games), are difficult to express and solve in the classical constraint satisfaction problem. This thesis is concerned with an extension to the classical problem: the Quantified Constraint Satisfaction Problem (QCSP). QCSP has recently attracted interest. In QCSP, quantifiers are allowed, facilitating the expression of uncertainty.I examine whether QCSP is a useful formalism. This divides into two questions: whether QCSP can be solved efficiently; and whether realistic problems can be represented in QCSP. In attempting to answer these questions, the main contributions of this thesis are the following:
These are set in context by a thorough review of the QCSP literature. 

Available as: PDF  
2007  Robert Brignall 
Simplicity in Relational Structures and its Application to Permutation Classes  
The simple relational structures form the units, or atoms, upon which all other relational structures are constructed by means of the substitution decomposition. This decomposition appears to have first been introduced in 1953 in a talk by Fraïssé, though it did not appear in an article until a paper by Gallai in 1967. It has subsequently been frequently rediscovered from a wide variety of perspectives, ranging from game theory to combinatorial optimization.Of all the relational structures – a set which also includes graphs, tournaments and posets – permutations are receiving ever increasing amounts of attention. A simple permutation is one that maps every nontrivial contiguous set of indices to a set of indices that is never contiguous. Simple permutations and intervals of permutations are important in biomathematics, while permutation classes – downsets under the pattern containment order – arise naturally in settings ranging from sorting to algebraic geometry.We begin by studying simple permutations themselves, though always aim to establish this theory within the broader context of relational structures. We first develop the technology of “pin sequences”, and prove that every sufficiently long simple permutation must contain either a long horizontal or parallel alternation, or a long pin sequence. This gives rise to a simpler unavoidable substructures result, namely that every sufficiently long simple permutation contains a long alternation or oscillation.
Erdõs, Fried, Hajnal and Milner showed in 1972 that every tournament could be extended to a simple tournament by adding at most two additional points. We prove analogous results for permutations, graphs, and posets, noting that in these three cases we may need to extend a structure by adding ⌈(n + 1)/2⌉ points in the case of permutations andposets, and log_{2} (n + 1) points in the graph case. The importance of simple permutations in permutation classes has been well established in recent years. We extend this knowledge in a variety of ways, first by showing that, in a permutation class containing only finitely many simple permutations, every subset defined by properties belonging to a finite “querycomplete set” is enumerated by an algebraic generating function. Such properties include being an even or alternating permutation, or avoiding generalised (blocked or barred) permutations. We further indicate that membership of a permutation class containing only finitely many simple permutations can be computed in linear time. Using the decomposition of simple permutations, we establish, by representing pin sequences as a language over an eightletter alphabet, that it is decidable if a permutation class given by a finite basis contains only finitely many simple permutations. We also discuss possible approaches to the same question for other relational structures, in particular the difficulties that arise for graphs. The pin sequence technology provides a further result relating to the wreath product of two permutation classes, namely that C≀ D is finitely based whenever D does not admit arbitrarily long pin sequences. As a partial converse, we also exhibit a number of explicit examples of wreath products that are not finitely based. 

Available as: Postscript PDF  
2007  Stephen D. Waton 
On Permutation Classes Defined by Token Passing Networks, Gridding Matrices and Pictures: Three Flavours of Involvement  
The study of pattern classes is the study of the involvement order on finite permutations. This order can be traced back to the work of KNuth. In recent years the area has attracted the attention of many combinatorialists and there have been many structural and enumerative developments. We consider permuations classes defined in three different ways and emonstrate that asking the same fixed questions in each case motivates a different view of involvement. Token passing networks encourage us to consider permutations as sequence of integers; grid classes encourage us to consider them as point sets; picture classes, which are developed for the first time in this thesis, encourage a purely geometrical approach. As we journey through each area we present several new results.We begin by studying the basic definitions of a permutation. This is followed by a discussion of the questions one would wish to ask permutatation classes. We concentrate on four particular areas: partial well order, finite basis, atomicity and enumeration. Our third chapter asks these questions of token passing networks; we also develop the concept of completeness and show that it is decidable whether or not a particular network is complete. Next we move onto grid classes, our analysis using generic sets tields an algorithm for determining when a class grid is atomic; we also present a new and elegant proof which demonstrates that certain grid classes are partially well ordered.The final chapter comprises the development and analysis of picture classes. We completely classify and enumerate those permutations which can be drawn from a circle, those which can be drawn from an X and those which can be drawn from some complex polygon. We exhibit the first uncountable set of closed classes to be found in a natural setting; each class is drawn from three parallel lines. We present a permutation version of the famous ‘happy ending’ problem of Erdos and Szekeres. We conclude with a discussion of permutation classes in higher dimensional space.  
Available as: PDF  
2006  Nelson Silva 
Computing with Permutations and Transformations  
Inspired by the results of D. McAlister, we consider transformation semigroups generated by an ncycle and a transformation of rank 2. We give structural properties of the generator of rank 2 which determine if the semigroup is regular or completely regular. We also show that there are no inverse semigroups of the type considered.Using similar techniques, we determine all possible sizes for a given semigroup of this type. This is done via a complete description of the Green’s relations of the semigroup.In the next stage of this thesis we are concerned with the study of the isomorphism between two members of this class of semigroups. We give conditions in order to decide if two given semigroups are isomorphic. In the process of answering this question, we study presentations for these semigroups, which are then used as another tool for the study of isomorphisms.
Due to the combinatorial and algorithmic character of the properties defined in this thesis, the computer algebra system GAP played an important role in our studies both as a tool for testing examples and as a tool for making conjectures. All the formal algorithms resulting from out work are also given. In the last part of our thesis we study a different kind of problem. Having as a starting point the famously known “Sierpinski’s Lemma” and the proof of this lemma given by Banach, we give a generalisation of this result. We prove that every countable set of endomorphisms of an algebra A which has an infinite basis in a 2generated subsemigroup of the semigroup of all endomorphisms of A. Several corollaries of this result follow, among them the case where A is an independence algebra. This result was first obtained by K.D. Magill, using a very complicated and complex proof that makes no use of Banach’s proof. 

Available as: PDF  
2006  Elizabeth Kimber 
Cyclically Generated Finite Groups  
A finite group is cyclically generated if it has an automorphism that cycles through a generating set for the group. We present results that help us to determine whether a given group is cyclically generated without first identify ing its automorphism group. Using these techniques we establish conditions under which certain familiar groups are cyclically generated and, in partic ular, we prove that every finite abelian group is cyclically generated. With the emphasis on groups that are the direct product of a cyclic group and a nonabelian group, we investigate necessary and sufficient conditions for a direct product to be cyclically generated.The question of when a finite abelian group has a minimal cyclic generating set is addressed in the second part of this thesis. As every symmetric generat ing set is a cyclic generating set, we can use a recent result about symmetric generating sets for abelian groups to find examples of abelian groups that have cyclic generating sets of minimum size. We explore the connection be tween automorphisms, matrices, and roots of certain polynomials over rings of prime power order to construct suitable automorphisms or prove that no such automorphism exists. We prove necessary and sufficient conditions for a finite abelian group of rank 3 or 4 to have a minimal cyclic generating set, and also for an abelian group of rank 5 if the order of the group is not divisible by 5. Finally, we present partial results for abelian groups of higher prime and square free rank.  
Available as: PostScript PDF  
2006  Dale Sutherland 
ComputerAssisted Proofs and the F^{a,b,c} Conjecture  
This thesis studies finitely presented groups and the process known as coset enumeration, which finds the index of a finitely generated subgroup in a finitely presented group, provided this index is finite. The ToddCoxeter algorithm for coset enumeration is described, as well as its modified version, additionally finding a presentation for the subgroup. Coset enumeration is suitable for computer implementation, and GAP and ACE, two programs containing such functions using different strategies, are outlined.Proof Extraction After Coset Enumeration (PEACE) is a computer program that allows one to show a group element is in the subgroup. Descriptions are provided of modifications to PEACE, giving this program the extra functionality of creating subgroup presentations with the Modified ToddCoxeter algorithm. Using different strategies during the enumeration to determine varied subgroup presentations is also discussed. Additionally, a program converting the output of the original PEACE program, showing an element’s membership of the subgroup, into a lemmabased step by step proof is implemented and described.’The F^{a,b,c} conjecture’ was proposed by Campbell, Coxeter and Robertson in 1977 to classify the groups F^{a,b,c}= (r, sr^{2}, rs^{a}rs^{b}rs^{c}) by considering the homomorphic image H^{ a,b,c} = (r, sr^{2}, rs^{a}rs^{b}rs^{c}, s^{2(a+b+c)}).
The lemmabased proof generating program is used as an aid in considering the groups F^{a,b,c} and the corresponding conjecture. Lastly, a proof showing this conjecture to be true is provided. 

Available as: PostScript PDF  
2005  Peter Gallagher 
On the Finite Generation and Presentability of Diagonal Acts, Finitary Power Semigroups and Schützenberger Products  
The diagonal right act of a semigroup S is the set S x S , with S acting by componentwise multiplication from the right. The diagonal left act of S and the diagonal biact of S are defined analogously.Necessary and sufficient conditions are found for the finite generation of the diagonal biacts of completely zerosimple semigroups, completely simple semigroups and Clifford semigroups. It is also proved that various classes of semigroups do not have finitely generated or cyclic diagonal right, left or biacts.The semigroups of full transformations, partial transformations and binary relations on an infinite set each have cyclic diagonal right and left acts. The semigroup of full finitetoone transformations on an infinite set has a cyclic diagonal right act but its diagonal left act is not finitely generated. The semigroup of partial injections on an infinite set has neither finitely generated diagonal right nor left act, but has a cyclic diagonal biact.The finitary power semigroup of a semigroup S , denoted P_{f} (S), is the set of finite subsets of S with respect to the usual set multiplication. We show that P_{f} (S) is not finitely generated if S is an infinite semigroup in any of the following classes: commutative; BruckReilly extensions; inverse semigroups that contain an infinite group; completely zerosimple; completely regular.
Finally, the finite generation and presentability of Schützenberger products are investigated. A necessary and sufficient condition is established for finite generation. The Schützenberger product of two groups is finitely presented as an inverse semigroup if and only if the groups are finitely presented, but is not finitely presented as a semigroup unless both groups are finite. 

Available as: PostScript PDF  
2005  Maja Waldhausen 
On an Algorithm for Enumerating Generating Sets of Modules over Euclidean Domains  
In this thesis a method for the enumeration of generators of modules over ordered Euclidean domains is presented. This method is based on the ideas of the coset enumeration algorithm for subgroups of finitely presented groups. The coset enumeration algorithm has first been described by J. Todd and H. Coxeter as a method for hand calculation.G. Labonté and S. Linton independently developed a linear version of the coset enumeration algorithm, the socalled vector enumeration algorithm. There a finitely presented module M over a finitely presented kalgebra is required, where k denotes a field. The vector enumeration procedure computes a basis B of M considered as module over k, together with a matrix representation that describes the action of the algebra generators on the elements of the basis B.We shall present a generalisation of the vector enumeration procedure. This procedure is called the module generator enumeration procedure or, abbreviated, the MGEprocedure. We extend here to the case where we are not given a field k but a Euclidean domain instead. This case is more complicated since the elements of a domain that is not a field do not necessarily have inverses. Moreover, a module over a domain does not generally have a basis: such a module can have torsion. As a consequence of this, the MGEprocedure must possibly handle exceedingly large numbers, but also vectors of large size.In this thesis we present a result for certain submodules of modules which are part of the input of the MGEprocedure. This result corresponds to a theorem by O. Schreier on presentations of subgroups of finite index of finitely presented groups. We shall prove that for a submodule N of a finitely generated and free module in a certain situation a finite generating set exists. This result will be applied to modules that are connected to the input of the MGEprocedure in order to prove termination of the MGEprocedure.
Moreover, we link subroutines of the MGEprocedure to concepts of Gröbner bases and prefix Gröbner bases of modules over Euclidean domains.These connections shall be used in order to show correctness and termination of the procedure. We also demonstrate how a finite set of generators for a submodule N, that satisfies the preconditions of the equivalent of the SchreierTheorem, can be extracted from the output when the MGEprocedure has terminated. We construct relations on these generators which yields a presentation of N in terms of the generators given. This construction forms a linear analogue of the modified ToddCoxeter procedure. The MGEprocedure as well as the extended version for the construction of a submodule presentation have been implemented in GAP as part of this thesis. We will give an outline of the strategy of the MGEprocedure as it has been implemented and we give a description of the main subroutines in pseudocode. We discuss results and runtimes of some examples of the MGEprocedure and we give a conclusion and an outlook of the MGEprocedure as it has been implemented in GAP.


Available as: PDF  
2005  Catarina Carvalho 
Generation and Presentations of Semigroup Constructions: BruckReilly Extensions and Psemigroups  
In this thesis we study problems regarding finite presentability of Bruck Reilly extensions, finite generation of the underlying monoids, and finite generation of Eunitary inverse semigroups.The first main question we consider is: Let M be a monoid and θ and endomorphism of M. If the Bruck Reilly extension BR(M,θ) is finitely presented is the monoid M necessarily finitely generated? We answer this question for the following classes of monoids: semilattices; Clifford monoids; zero monoids; free monoids; completely (0)simple semigroups; and semidirect products of semilattices by groups. This allows us to obtain necessary and sufficient conditions for the Bruck Reilly extensions of these classes of monoids to be finitely presented.We also show that, like the free inverse monoid, a Bruck Reilly extension (of an inverse monoid) is not necessarily finitely presented as a monoid when it happens to be finitely presented as an inverse monoid.We then consider the question: When are Psemigroups, or Eunitary inverse semigroups finitely generated? We give necessary and sufficient conditions for a Psemigroup P(G,X,Y) to be finitely generated in the case when X\Y is finite, and consider several particular cases when X\Y is infinite.  
Available as: PostScript PDF  
2005  Alan Cain 
Presentations for Subsemigroups of Groups  
This thesis studies subsemigroups of groups from three perspectives: automatic structures, ordinary semigroup presentations, and Malcev presentations. [A Malcev presentation is a presentation of a special type for a semigroup that can be embedded into a group. A groupembeddable semigroup is Malcev coherent if all of its finitely generated subsemigroups admit finite Malcev presentations.] The theory of synchronous and asynchronous automatic structures for semigroups is expounded, particularly for groupembeddable semigroups. In particular, automatic semigroups embeddable into groups are shown to inherit many of the pleasant geometric properties of automatic groups. It is proved that groupembeddable automatic semigroups admit finite Malcev presentations, and such presentations can be found effectively. An algorithm is exhibited to test whether an automatic semigroup is a free semigroup. Cancellativity of automatic semigroups is proved to be undecidable. Study is made of several classes of groups: virtually free groups; groups that satisfy semigroup laws (in particular [virtually] nilpotent and [virtually] abelian groups); polycyclic groups; free and direct products of certain groups; and onerelator groups. For each of these classes, the question of Malcev coherence is considered, together with the problems of whether finitely generated subsemigroups are finitely presented or automatic. This study yields closure and containment results regarding the class of Malcev coherent groups. The property of having a finite Malcev presentation is shown to be preserved under finite Rees index extensions and subsemigroups. Other concepts of index are also studied.  
Available as: PostScript PDF  
2005  Andrew Rowley 
A More Effective Use of Information in Search for Quantified Boolean Formulae  
The solving of Quantified Boolean Formulae (QBFs) has recently become of great interest. QBFs are an extension of the Satisfiability problem (SAT), which has been studied in depth. Many QBF techniques are built as extensions to SAT techniques. While this can be useful, it also means that QBF specific techniques have not received as much attention as they could.The contributions of this thesis are:
Overall, the better use of information is shown to lead to improvements in QBF solving techniques. 

Available as: PostScript PDF  
2004  Erzsebet Dombi 
Automatic Sacts and inverse semigroup presentations  
To provide a general framework for the theory of automatic groups and semigroups, we introduce the notion of an automatic semigroup act. This notion gives rise to a variety of definitions for automaticity depending on the set chosen as a semigroup act. Namely, we obtain the notions of automaticity, Schutzenberger automaticity, R and Lclass automaticity, etc. We discuss the basic properties of automatic semigroup acts. We show that if S is a semigroup with local right identities, then automaticty of a semigroup act is independent of the choice of both the generators of S and the generators of the semigroup act. We also discuss the equality problem of automatic semigroup acts. To give a geometric approach, we associate a directed labelled graph to each Sact and introduce the notion of the fellow traveller property in the associated graph. We verify that if S is a regular semigroup with finitely many idempotents, then Schutzenberger automaticity is characterized by the fellow traveller property of the Schutzenberger graph. We also verify that a Schutzenberger automatic regular semigroup with finitely many idempotents is finitely presented. We end Chapter 3 by proving that an inverse free product of Schutzenberger automatic inverse semigroups is Schutzenberger automatic. In Chapter 4, we first introduce the notion of finite generation and finite presentability with respect to a semigroup action. With the help of these concepts we give a necessary and sufficient condition for a semidirect product of a semilattice by a group to be finitely generated and finitely presented as an inverse semigroup. We end Chapter 4 by giving a necessary and sufficient condition for the semidirect product of a semilattice by a group to be Schutzenberger automatic. Chapter 5 is devoted to the study of HNN extensions of inverse semigroups from finite generation and finite presentability point of view. Namely, we give necessary and sufficient conditions for finite presentability of Gilbert’s and Yamamura’s HNN extension of inverse semigroups. The majority of the results contained in Chapter 5 are the result of a joint work with N.D. Gilbert and N. Ruskuc.  
Available as: PostScript PDF  
2003  Peter Campbell 
Fibonacci length and efficiency in group presentations  
In this thesis we shall consider two topics that are contained in combinatorial group theory and concern properties of finitely presented groups. The first problem we examine is that of calculating the Fibonacci length of certain families of finitely presented groups. In pursuing this we come across ideas and unsolved problems from number theory. We mainly concentrate on finding the Fibonacci length of powers of dihedral groups, certain Fibonacci groups and a family of metacyclic groups.The second problem we investigate in this thesis is finding if the group P GL(2, p), for p a prime, is efficient on a minimal generating set. We find various presentations that define P GL(2, p) or C2 x P S L(2, p) and direct products of these groups. As in the previous sections we come across number theoretic problems. We also have occasion to use results from tensor theory and homological algebra in order to obtain our results.  
Available as: PostScript PDF  
2002  James David Mitchell 
Extremal problems in combinatorial semigroup theory  
In this thesis we shall consider three types of extremal problems (i.e. problems involving maxima and minima) concerning semigroups.In the first chapter we show how to construct a minimal semigroup presentation that defines a group of nonnegative deficiency given a minimal group presentation for that group. This demonstrates that the semigroup deficiency of a group of nonnegative deficiency is equal to the group deficiency of that group. Given a finite monoid we find a necessary and sufficient condition for the monoid deficiency to equal the semigroup deficiency. We give a class of infinite monoids for which this equality also holds.The second type of problem we consider concerns infinite semigroups of relations and transformations. We find the relative rank of the full transformation semigroup, over an infinite set, modulo some standard subsets and subsemigroups, including the set of contraction maps and the set of order preserving maps (for some infinite ordered sets). We also find the relative rank of the semigroup of all binary relations (over an infinite set) modulo the partial transformation semigroup, the full transformation semigroup, the symmetric inverse semigroup, the symmetric group and the set of idempotent relations. Analogous results are also proven for the symmetric inverse semigroup.The third, and final, type of problem studied concerns generalising notions of independence from linear algebra to semigroups and groups. We determine the maximum cardinality of an independent set in finite abelian groups, Brandt semigroups, free nilpotent semigroups, and some examples of infinite groups.  
Available as: PostScript PDF  
2002  Luis Descalco 
Automatic semigroups: constructions and subsemigroups  
In this thesis we start by considering conditions under which some standard semigroup constructions preserve automaticity. We first consider Rees matrix semigroups over a semigroup, which we call the base, and work on the following questions:
We also consider similar questions for BruckReilly extensions of monoids and wreath products of semigroups. Then we consider subsemigroups of free products of semigroups and we study conditions that guarantee them to be automatic. Finally we obtain a description of the subsemigroups of the bicyclic monoid that allow us to study some of their properties, which include finite generation, automaticity and finite presentability. 

Available as: PostScript PDF  
2001  Rob Wainwright 
Finding “small” matrices P, Q such that PDQ = S  
This thesis addresses the problem of finding matrices which reduce a given integer matrix to its Smith normal form where the matrix entries are as small as possible  
Available as: PostScript PDF 
MSc dissertations
2004  Robert Brignall 
Pattern classes of permutations: constructions, atomicity and the finite basis property  
A structure on sets of permutations based on involvement is defined, which forms a partial order on the set of all finite permutations. Sets with this structure we call closed classes, and we show how these can be expressed in terms of its Basis, or pattern avoidance set. Further structures on permutations and classes are introduced, in particular the notion of Atomic Classes. We provide a list of constructions to form new classes from old, and, for each construction, discuss the existence of a Finite Basis for the new class, and the conditions required for this class to be Atomic. Particular emphasis is placed on the Wreath Product, where we exhibit the only known Finite Basis result. A new method for proving the Finite Basis result for the wreath product X ≀ I is exhibited, and this is then adapted and applied to several other related wreath products to prove the Finite Basis Property in each case, all of which were previously unknown.  
Available as: PostScript PDF  
2002  Elizabeth Kimber 
Some cyclically presented groups  
In 1999, D.L. Johnson, A.C. Kim and E.A. O’Brien proved that the corresponding groups in two pairs of infinite families of cyclically presented groups are isomorphic. The details of their proofs are given here. Upper and lower bounds for the size of a minimum generating set for the groups in each family were proved in 2001 by M.F. Newman, with an indication that smaller upper bounds could be found. Proofs of Newman’s bounds are given, and the proof of a smaller upper bound, which is a new result, completes this dissertation.  
Available as: PostScript PDF  
2002  Katrin E. Gehles 
Ordinary characters of finite special linear groups  
The main objective of this thesis is to give a comprehensive account of the construction of the character table ofSL(2,p^{k}), p a prime. From this result we derive the character table of PSL(2,p^{k}), p a prime. The theoretical background which is required to understand the construction process is developed in considerable detail. This description also gives a first impression of the representation and character theory of finite groups. The strong emphasis lies on ordinary rather than modular representation and character theory. Many theorems and proofs are presented both in the language of representations and characters and in terms of modules. We then demonstrate the capabilities of the computer program GAP in applications to ordinary character tables using the example of SL(2,5).  
Available as: PostScript PDF  
2002  Catarina Carvalho 
Presentations of semigroups and inverse semigroups  
It is known that a group is finitely presented as a group if and only if it is finitely presented as a monoid, and that a monoid is finitely presented as a monoid if and only if it is finitely presented as a semigroup. A similar result does not hold for all inverse semigroups; the free inverse semigroup is an example of that. After describing the free inverse semigroup and see why it cannot be finitely presented as a semigroup, we look at two “classes” of inverse semigroups that are finitely presented as inverse semigroups if and only if they are finitely presented as semigroups, namely inverse monoids with finitely many left and right ideals and BruckReilly extensions of groups. In the last part of this dissertation we study BruckReilly extensions of Clifford monoids and prove that they are finitely presented as inverse semigroups if and only if they are finitely presented as semigroups. We also show that in some specific cases the BruckReilly extensions of a Clifford monoid, like the Clifford semigroups, are finitely presented if and only if its Dclasses are finitely presented.  
Available as: PostScript PDF 