2013/7
 Ian Gent, Chris Jefferson, Steve Linton, Ian Miguel, Peter Nightingale

 Finite State Automata for the Paper "Generating Custom Propagators for Arbitrary Constraints"


This brief technical report gives the finite state automata used in the paper "Generating Custom Propagators for Arbitrary Constraints" for the experiments with a decomposition of the Regular constraint.

 Available as
PDF

2013/6
 J.V. Jeppesen, R.A. Anderson, T.W. Kelsey, S.L. Christiansen, S.G. Kristensen, K. Jayaprakasan, N. RaineFenning, B.K. Campbell, and C. Yding Andersen

 Which follicles make the most antiMüllerian hormone in humans? Evidence for an abrupt decline in AMH production at the time of follicle selection


AntiMüllerian hormone (AMH) is exclusively produced by granulosa cells (GC) of the developing preantral and antral follicles, and AMH is increasingly used to assess ovarian function. It is unclear which size follicles make the most AMH (total content) and are the main contributors to circulating AMH concentrations. To determine AMH gene expression in GC (qRT–PCR) and follicular AMH production (Elisa and RIA) in relation to follicular development, 87 follicles (313 mm diameter) including both GC and the corresponding follicular fluid (FF) were collected in connection with fertility preservation of human ovaries. Further, follicle number and diameter, graded in 1 mm increments, were determined by 3D ultrasound in 113 women in their natural menstrual cycle to determine follicle number and diameter in relation to circulating AMH levels. This study demonstrates for the first time a positive association between AMH gene expression in human and both total follicular fluid AMH (P<0.02) and follicular fluid AMH concentration (P<0.01). AMH gene expression and total AMH protein increased until a follicular diameter of 8 mm, after which a sharp decline occurred. In vivo modelling confirmed that 58 mm follicles make the greatest contribution to serum AMH, estimated for the first time in human to be 60% of the circulating concentration. Significant positive associations between gene expression of AMH and FSHR, AR and AMHR2 expression (P<0.00001 for all three) and significant negative association between follicular fluid AMH concentration and CYP19a1 expression were found (P<0.0001). Both AMH gene expression (P<0.02) and follicular fluid concentration of AMH (P<0.00001) correlated negatively with estradiol concentration.

 Available as
PDF

2013/5
 Andreas Distler, Tom Kelsey

 The semigroups of order 9 and their automorphism groups


We report the number of semigroups with 9 elements up to isomorphism or antiisomorphism to be 52989400714478 and up to isomorphism to be 105978177936292. We obtained these results by combining computer search with recently published formulae for the number of nilpotent semigroups of degree 3. We further provide a complete account of the automorphism groups of the semigroups with at most 9 elements. We use this information to deduce that there are 148 195 347 518 186 distinct associative binary operations on an 8element set and 38447365355811944462 on a 9element set.

 Available as
PDF

2013/4
 Lars Kotthoff, Tom Kelsey and Martin McCaffery

 A framework for largescale distributed AI search across disconnected heterogeneous infrastructures


We present a framework for a largescale distributed eScience Artificial Intelligence search. Our approach is generic and can be used for many different problems. Unlike many other approaches, we do not require dedicated machines, homogeneous infrastructure or the ability to communicate between nodes. We give special consideration to the robustness of the framework, minimising the loss of effort even after total loss of infrastructure, and allowing easy verification of every step of the distribution process. In contrast to most eScience applications, the input data and specification of the problem is very small, being easily given in a paragraph of text. The unique challenges our framework tackles are related to the combinatorial explosion of the space that contains the possible solutions and the robustness of longrunning computations. Not only is the time required to finish the computations unknown, but also the resource requirements may change during the course of the computation. We demonstrate the applicability of our framework by using it to solve a challenging and hitherto open problem in computational mathematics. The results demonstrate that our approach easily scales to computations of a size that would have been impossible to tackle in practice just a decade ago.

 Available as
PDF

2013/3
 C Xiong, TW Kelsey, SA Linton and U Leonhardt

 The computation of Casimir forces for inhomogeneous planar media


Casimir forces arise from vacuum fluctuations. They are fully understood only for simple models, and are important in nano and microtechnologies. We report our experience of computer algebra calculations towards the Casimir force for models involving inhomogeneous dielectrics. We describe a methodology that greatly increases confidence in any results obtained, and use this methodology to demonstrate that the analytic derivation of scalar Green’s tensors is at the boundary of current computer algebra technology. We further demonstrate that Lifshitz theory of electromagnetic vacuum energy can not be directly applied to calculate the Casimir stress for models of this type, and produce results that have led to alternative regularizations. Using a combination of our new computational framework and the new theory based on our results, we provide specific calculations of Casimir forces for planar dielectrics having permittivity that declines exponentially. We discuss the relative strengths and weaknesses of computer algebra systems when applied to this type of problem, and describe a combined numerical and symbolic computational framework for calculating Casimir forces for arbitrary planar models.

 Available as
PDF

2013/2
 WH Wallace, TW Kelsey, RA Anderson

 Ovarian cryopreservation: experimental or established and a cure for the menopause?


Longterm (>7 years) duration of function of ovarian cortical tissue grafts in three patients who have had several successful pregnancies is encouraging and requires us to carefully examine the risk benefit analysis of this technique for our future patients.However, the success rate for ovarian cryopreservation is unclear as the denominator (the number of women in whom frozenthawed ovarian tissue has been reimplanted) is unknown. There still remain many unknowns and much more research is required before ovarian transplantation can be considered standard practice. The ability of ovarian cryopreservation to preserve fertility for some young survivors of cancer is proven, but the indications for which patients should be offered this exciting new technology are not yet established.

 Available as
PDF

2013/1
 Thomas W. Kelsey, Sarah K. Dodwell, A. Graham Wilkinson, Tine Greve, Claus Y. Andersen, Richard A. Anderson, Hamish B. Wallace

 Ovarian volume throughout life: a validated normative model


The measurement of ovarian volume has been shown to be a useful indirect indicator of the ovarian reserve in women of reproductive age, in the diagnosis and management of a number of disorders of puberty and adult reproductive function, and is under investigation as a screening tool for ovarian cancer. To date there is no normative model of ovarian volume throughout life. By searching the published literature for ovarian volume in healthy females, and using our own data from multiple sources (combined n = 59,994) we have generated and robustly validated the first model of ovarian volume from conception to 82 years of age. This model shows that 69% of the variation in ovarian volume is due to age alone. We have shown that in the average case ovarian volume rises from 0.7 mL at 2 years of age to a peak of 7.7 mL at 20 years of age with a subsequent decline to about 2.8mL at the menopause and smaller volumes thereafter. Our model allows us to generate normal values and ranges for ovarian volume throughout life. This is the first validated normative model of ovarian volume from conception to old age; it will be of use in the diagnosis and management of a number of diverse gynaecological and reproductive conditions in females from birth to menopause and beyond.

 Available as
PDF

2012/2
 Peter Nightingale, Ian Gent, Chris Jefferson and Ian Miguel

 Short and Long Supports for Constraint Propagation


Constraint solvers typically employ a systematic backtracking search, interleaving the choice of an instantiation of a decision variable with the propagation of the constraints to determine the consequences of the choice made. Specialpurpose constraint propagation algorithms (such as those for the element constraint) frequently make implicit use of short supports  by examining a subset of the variables, they can infer support (a justification that a variable, value pair may still form part of an assignment that satisfies the constraint) for all other variables and values and save substantial work. However, to date general purpose propagation algorithms rely upon supports involving all variables. We demonstrate how to employ short supports in a new general purpose propagation algorithm called ShortGAC. Experiments demonstrate the efficiency of ShortGAC compared with other generalpurpose propagation algorithms.
We identify inefficiencies in ShortGAC, and introduce a new algorithm HaggisGAC to address these. Experiments show HaggisGAC performing better on short supports than ShortGAC, and better than GACSchema on full length supports. Thus HaggisGAC is an excellent general purpose GAC algorithm for dealing with either short or long supports. We also show how it can be adapted to avoid work on backtracking. In some cases this can lead to significant reductions in memory use. To summarise, we have demonstrated the value of the explicit use of short supports, and introduced algorithms to exploit them, of which HaggisGAC seems to be the best.
All the proposed algorithms are excellent for propagating disjunctions of constraints. In all experiments with disjunctions we found our algorithms to be faster than Constructive Or (Lagerkvist & Schulte, 2009) and GACSchema (Bessièere & Régin, 1997) by at least an order of magnitude, and up to three orders of magnitude.

 Available as
PDF

2012/1
 Ian Gent

 An Optimality Result on Maintaining List Pointers During Backtracking Search


I prove that a widely used technique for scanning lists in backtracking search algorithms has excellent optimality properties. The result applies to a simple general framework, which I present. It applies to critical algorithms such as watched literal unit propagation in SAT and important algorithms for maintaining generalised arc consistency in constraint satisfaction. I now show that both these techniques have optimal run time per branch in bigO terms when amortized across a search tree. Moreover the constant factor overhead of the worst case is only 2 in the simplest case. It is widely known that these methods are highly space efficient and effective in practice. My results help to explain this from a theoretical point of view.

 Available as
PDF

2011/1
 Max Neunhoffer, Markus Pfeiffer and Nik Ruskuc

 Deciding Word Problems of Semigroups Using Finite State Automata


We explore a natural class of semigroups that have word problem decidable by finite state automata. Among the main results are invariance of this property under change of generators, invariance under basic algebraic constructions and properties of the group of units.

 Available as
PDF

2010/12
 V A Bovdi, A B Konovalov and S Linton

 Torsion Units in Integral Group Rings of Conway Simple Groups


Using the LutharPassi method, we investigate the possible orders
and partial augmentations of torsion units of the normalized unit group of
integral group rings of Conway simple groups Co_{1} , Co_{2} and Co_{3} .

 Available as
PDF

2010/11
 Thomas W Kelsey, Phoebe Wright, Scott M Nelson, Richard A Anderson and W Hamish B Wallace

 A validated model of serum antiMüllerian hormone from conception to menopause reflects ovarian activity throughout life


AntiMüllerian hormone (AMH) is a product of growing ovarian follicles. Its concentration in blood
may also reflect the nongrowing follicle (NGF) pool (the ovarian reserve) and the rate of activation
of follicle growth, and be of value in determining likely age at menopause. We have established AMH
concentrations in women from age 0.3 to 59 years, using published data from normal women (n=1099),
and generated a model. This was then validated using a second, independent database of similar size.
The model demonstrates a rise in serum AMH to a peak at age 19.6 years, followed by a decline to
the menopause, and allows the generation of normative data at all ages. During both childhood and
adolescence and in adulthood, there were very close positive relationships between rate of loss of NGF
pool, ie rate of initiation of follicle growth, whereas AMH showed a negative relationship to total NGF
during childhood and adolescence and a positive relationship thereafter. This model indicates that AMH
concentrations reflect NGF numbers and follicle growth initiation from birth to the menopause, and that
there is a transition period in early adulthood when AMH starts to reflect the progressive loss of the
ovarian reserve.

 Available as
PDF

2010/10
 T W Kelsey and W H B Wallace

 Machine Science in Biomedicine: Practicalities, Pitfalls and Potential


Machine Science, or Datadriven Research, is a
new and interesting scientific methodology that uses advanced
computational techniques to identify, retrieve, classify and
analyse data in order to generate hypotheses and develop
models. In this paper we describe three recent biomedical
Machine Science studies, and use these to assess the current
state of the art with specific emphasis on data mining, data
assessment, costs, limitations, skills and tool support.

 Available as
PDF

2010/09
 Alexander Konovalov

 Rewriting the check of 8rewritability for A_{5}


The group G is called nrewritable for n > 1, if for each sequence of
n elements x_{1} , x_{2} , . . . , x_{n}
∈ G there exists a nonidentity permutation σ ∈ S_{n}
such that x_{1} x_{2}
. . . x_{n} = x_{σ(1)} x_{σ(2)} . . . x_{σ(n)}. Using computers, Blyth and
Robinson (1990) verified that the alternating group A_{5} is 8rewritable. We
report on an independent verification of this statement using the computa
tional algebra system GAP, and compare the performance of our sequential
and parallel code with the original one.

 Available as
PDF

2010/8
 Ian P Gent, Ian Miguel and Neil C A Moore

 An Empirical Study of Learning and Forgetting Constraints


Conflictdriven constraint learning provides big gains on many
CSP and SAT problems. However, time and space costs to propagate
the learned constraints can grow very quickly, so constraints are often
discarded (forgotten) to reduce overhead. We conduct a major empirical investigation into the overheads introduced by unbounded constraint
learning in CSP. This is the first such study in either CSP or SAT. We
obtain two significant results. The first is that a small percentage of
learnt constraints do most propagation. While this is conventional wisdom, it has not previously been the subject of empirical study. Second,
we show that even constraints that do no effective propagation can incur
significant time overheads. Finally, by implementing forgetting, we confirm that it can significantly improve the performance of modern learning
CSP solvers, contradicting some previous research.

 Available as
PDF

2010/7
 Tom Kelsey and Lars Kotthoff

 The Exact Closest String Problem as a Constraint Satisfaction Problem


We report (to our knowledge) the first evaluation of Constraint Satisfaction as a computational
framework for solving closest string problems. We show that careful consideration of symbol occurrences can provide search heuristics that provide several orders of magnitude speedup at and above
the optimal distance. We also report (to our knowledge) the first analysis and evaluation  using any
technique  of the computational difficulties involved in the identification of all closest strings for a
given input set. We describe algorithms for webscale distributed solution of closest string problems,
both purely based on AI backtrack search and also hybrid numericAI methods.

 Available as
PDF

2010/6
 Thomas W. Kelsey, Benedicta Casterta, Luis Castillo, W. Hamish B. Wallace and Francisco Coppola Gonzalvez

 Proliferating Cell Nuclear Antigen (PCNA) Allows the Automatic Identification of Follicles in Microscopic Images of Human Ovarian Tissue


Human ovarian reserve is defined by the population of nongrowing follicles (NGFs) in the ovary. The
estimation of ovarian reserve involves the identification of NGFs in prepared ovarian tissue. Previous
studies involving human tissue have used hematoxylin and eosin (HE) stain, with NGF populations
estimated by human examination either of tissue under a microscopic, or of images taken of this tissue. In
this study we replace HE with Proliferating Cell Nuclear Antigen (PCNA), and automate the identification
and enumeration of NGFs that appear in the resulting microscopic images. Our results both replicate and
improve on those of previous studies involving rodent ovaries, and demonstrate the viability of largescale
studies of human ovarian reserve using a combination of immunohistochemistry and computational image
analysis techniques.

 Available as
PDF

2010/5
 T W Kelsey

 The automatic identification of nongrowing follicles in human ovaries


The human ovary contains a fixed number of nongrowing follicles (NGF) established before birth; this number declines with increasing age culminating in the menopause at 5051 years on average.
NGF populations are estimated using a standard methodology: the ovary is fixed, thin slices (5  20µm) are taken
at regular intervals, and these are stained with hematoxylin and eosin (HE). Sample regions are photographed,
with the NGFs appearing in these images counted by hand. Assuming an even distribution of NGFs throughout
the ovary, the population is estimated using solutions of the corpuscle problem for 3dimensional specimens. This
process is time consuming, and suffers from human misclassification, integration error due to small sample sizes,
and the inconsistent assumption of even distribution. In his seminal paper from 1951, Block provided the
motivation for this study:
...The distribution of these follicles in human ovaries is so uneven that reliable values can not be
obtained until all the follicles are counted. This requires complete serial sectioning, which for a
woman of fertile age means one thousand five hundred to two thousand five hundred 20µm sections
per ovary. Under these circumstances any large scale investigation is impracticable....
We report a process of automatic feature detection leading to reduced human and sampling errors at low magnification which can, in principle, be used to obtain almost exact NGF populations from fully sectioned ovaries.

 Available as
PDF

2010/4
 T W Kelsey and W H B Wallace

 The dynamics of human ovarian reserve


The human ovary contains a fixed number of nongrowing follicles (NGF) established before birth that decline with increasing age culminating in the menopause at 5051 years. The objective of this study is to model the agerelated population of NGFs in the human ovary from conception to menopause.

 Available as
PDF

2010/3
 Peter Nightingale,

 The Extended Global Cardinality Constraint: An Empirical Survey


The Extended Global Cardinality Constraint (EGCC) is a vital component of
constraint solving systems, since it is very widely used to model diverse problems. The literature contains many different versions of this constraint, which
trade strength of inference against computational cost. In this paper, I focus on the highest strength of inference usually considered, enforcing generalized arc consistency (GAC) on the target variables. This work is an extensive empirical survey of algorithms and optimizations, considering both GAC on the target variables, and tightening the bounds of the cardinality variables. I evaluate a number of key techniques from the literature, and report important implementation details of those techniques, which have often not been described in published papers. Two new optimizations are proposed for EGCC. One of the
novel optimizations (dynamic partitioning, generalized from AllDifferent) was
found to speed up search by 5.6 times in the best case and 1.56 times on average, while exploring the same search tree. The empirical work represents by far the most extensive set of experiments on variants of GAC algorithms for EGCC. Overall, the best combination of optimizations gives a mean speedup of over 50 times compared to the same implementation without the optimizations.

 Available as
PDF

2010/2
 Ian P. Gent, Lars Kotthoff, Ian Miguel, Neil C A Moore, Peter Nightingale and Karen Petrie 
 Learning When to Use Lazy Learning in Constraint Solving


Learning in the context of constraint solving is a technique by which previously unknown constraints are uncovered during search and used to speed up subsequent search. Recently, lazy learning, similar to a successful idea from satisfiability modulo theories solvers, has been shown to be an effective means of incorporating constraint learning into a solver. Although a powerful technique to reduce search in some circumstances, lazy learning introduces a
substantial overhead, which can outweigh its benefits. Hence, it is desirable to know beforehand whether or not it is expected to be useful. We approach this problem using machine learning (ML). We show that, in the context of a large benchmark set, standard ML approaches can be used to learn a simple, cheap classifier which performs well in identifying instances on which lazy learning should or should not be used. Furthermore, we demonstrate significant performance improvements of a system using our classifier and the lazy learning and standard constraint solvers over a standard solver. Through rigorous
crossvalidation across the different problem classes in our benchmark set, we show the general applicability of our learned classifier.

 Available as
PDF

2010/1
 Andrea Rendl, Ian Miguel and Ian P. Gent 
 Optimising Quantified Expressions in the Automated Constraint Modelling Tool TAILOR


Constraint Programming (CP) is a powerful technique for
solving largescale combinatorial (optimisation) problems.
However, CP is often inaccessible to users without expert
knowledge in the area, precluding its widespread use. One
of the key difficulties lies in formulating an effective constraint model of an input problem for input to a constraint
solver. Automated Constraint Modelling tools address this
issue by providing assistance in model formulation. TAILOR is one such modelling tool. It incorporates a number of
highly effective model optimisations, which can compensate
for a wide selection of poor modelling choices that novices
(but also experts) often make. In the context of TAILOR,
this paper presents new constraint model optimisation
techniques concerned with optimising quantified expressions,
constructs that are commonly used in highlevel constraint
modelling languages, similar to forloops in programming
languages. Our experimental results show that quantified
expression optimisations can reduce solving time very
considerably.

 Available as
PDF

2009/23
 Alan J Cain, Robert Gray and Nik Ruskuc 
 Green Index in Semigroups: Generators, Presentations and Automatic Structures


Let S be a semigroup and let T be a subsemigroup of S. Then T acts on S by left and by right multiplication. This gives rise to a partition of
the complement of T in S, and to each equivalence class of this
partition we naturally associate a relative Schützenberger group. We
show how generating sets for S may be used to obtain generating sets for
T and the Schützenberger groups, and vice versa. We also give a method
for constructing a presentation for S from given presentations of T and
the Schützenberger groups. These results are then used to show that
several important properties are preserved when passing to finite Green
index subsemigroups or extensions, including: finite generation,
solubility of the word problem, growth type, automaticity, finite
presentability (for extensions) and finite Malcev presentability (in the
case of groupembeddable semigroups). These results provide common
generalisations of several classical results from group theory and Rees
index results from semigroup theory.

 Available as
PDF

2009/22
 Robert Brignall, Nik Ruskuc, and Vince Vatter 
 Simple Extensions of Combinatorial Structures


An interval in a combinatorial structure S is a set I of points which relate to every point from S \ I in the same way. A structure is
simple if it has no proper intervals. Every combinatorial structure
can be expressed as an inflation of a simple structure by structures
of smaller sizes  this is called the substitution (or modular) decomposition. In this paper we prove several results of the following type: An arbitrary structure S of size n belonging to a class C can be embedded into a simple structure from C by adding at most f(n) elements. We prove such results when C is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than 2. The function f(n) in these cases is 2,
⌈log2 (n + 1)⌉, ⌈(n + 1)/2⌉, ⌈(n + 1)/2⌉, ⌈log4 (n + 1)⌉, ⌈log3 (n + 1)⌉
and 1, respectively. In each case these bounds are best possible.

 Available as
PDF

2009/21
 Ian P. Gent, Chris Jefferson, Lars Kotthoff, Ian Miguel, and Peter Nightingale 
 Specification of the DOMINION Input Language Version 0.1


This document specifies the input language for the Dominion constraint solver synthesiser. This language is relatively lowlevel since it is intended to be the input for model analysis. It does, however, support the specification of problem classes, as well as problem instances. Its syntax is substantially influenced by that of Essence and Essence' but there are a number of differences, particularly in arrays and in Dominion's support for set and list comprehensions.

 Available as
PDF

2009/20
 Peter Nightingale 
 Are Adjacency Lists Worthwhile in AllDifferent?


In our AllDifferent paper [1], there was a loose end. The graph algorithms always discover the graph as they traverse it, by querying variable
domains. It might be more efficient to store the graph (and backtrack
it) in the form of adjacency lists. This is done here, and we show that it
doesn't affect the main conclusions of the paper.
[1] Ian P. Gent, Ian Miguel, and Peter Nightingale. Generalised arc consistency
for the alldifferent constraint: An empirical survey. Artificial Intelligence,
172(18):19732000, 2008.

 Available as
PDF

2009/19
 Elena Beratarbide and Tom Kelsey 
 eHealth Governance, A Key Factor for Better Health Care


In this chapter we develop a set of recommendations for aligning eHealth with
healthcare strategies. After introducing the key concepts we describe and discuss IT governance as a key enabler of successful alignment. We present outcomes from a study conducted in Scotland, and compare & contrast our preliminary results with those from similar studies in other countries. This analysis forms the basis of our set of recommendations, the most important of which are (a) to employ a wellknown and welldeveloped IT governance standard, (b) to ensure that the healthcare organisation has a high level of readiness for the transformation towards strategic alignment, and (c) to
utilize experts to direct and monitor both the organisational change and the eHealth alignment.
We want to stress the results presented in relation to perceived eHealthNHS
alignment are preliminary, even though we don't expect to obtain significant deviations compared with the results presented in advance on this chapter.

 Available as
PDF

2009/18
 R. Gray and N. Ruskuc 
 On Maximal Subgroups of Free Idempotent Generated Semigroups


The set of idempotents of an arbitrary semigroup has the
structure of a so called biordered set (or regular biordered set in the
case of von Neumann regular semigroups). These structures were studied
in detail in work of Nambooripad (1979) and Easdown (1985). There is a
notion of a free idempotent generated semigroup on a biordered set and
it was conjectured by McElwee in 2002 that the maximal subgroups of such
a semigroup are all free. The first counterexample to this conjecture
was given by Brittenham, Margolis and Meakin (2009), where it was shown
that the free abelian group of rank 2 is a maximal subgroup of the free
idempotent generated semigroup arising from a certain 72element
semigroup.
In this article we prove the following results:
(1) Every group is a maximal subgroup of some free idempotent generated
semigroup.
(2) Every finitely presented group is a maximal subgroup of some free
idempotent generated semigroup arising from a finite semigroup.
(3) Every group is a maximal subgroup of some free regular idempotent
generated semigroup.
(4) Every finite group is a maximal subgroup of some free regular
idempotent generated semigroup arising from a finite regular semigroup.

 Available as
PDF

2009/17
 C. Xiong, T.W. Kelsey, S.A. Linton and U. Leonhardt 
 Towards the calculation of Casimir forces for inhomogeneous planar media


Casimir forces arise from vacuum fluctuations. They are fully understood only
for simple models, and are important in nano and microtechnologies. We report our experience of computer algebra calculations towards the Casimir force for models involving inhomogeneous dielectrics. We describe a methodology that greatly increases confidence in any results obtained, and use this methodology to demonstrate that the analytic derivation of scalar Green's functions is at the boundatry of current computer algebra technology. We further demonstrate that Lifshitz theory of electromagnetic vacuum energy can not be directly applied to calculate the Casimir stress for models of this type, and produce results that indicate the possibility of alternative regularisations. We discuss the relative strengths and weaknesses of computer algebra systems
when applied to this type of problem, and suggest combined numerical and symbolic approaches towards a more general computational framework.

 Available as
PDF

2009/16
 Scott H. Murray and Colva M. RoneyDougal 
 Constructive Homomorphisms for Classical Groups


Let Ω ≤ GL_{d} (q) be a quasisimple classical group in its natural representation and let Δ = N_{GL d(q)}(Ω). We construct the projection from &Delta to Δ/Ω and provide fast, polynomialtime algorithms for computing the image of an element. Given a discrete logarithm oracle, we also represent Δ/Ω as a group with at most 3 generators and 6 relations. We then compute canonical representatives for the cosets of Ω. We describe applications of these methods to the matrix group recognition pro ject and conjugacy problems. A key ingredient of our algorithms is a new, asymptotically fast method for constructing isometries between spaces with bilinear or unitary forms.

 Available as
PDF

2009/15
 Andrea Rendl, Ian Miguel and Ian P. Gent 
 Effective Compilation of Constraint Models


Compiling solverindependent constraint models to solver
input typically involves flattening, the decomposition of complex expressions
into simpler expressions, introducing additional variables and constraints. In previous work [1], we have informally proposed extending flattening problem
instances with common subexpression elimination(CSE), a widespread optimisation technique that has not yet been established in Constraint Programming (CP). This paper extends our previous work with three main contributions. First, we formally analyse the cost of flattening instances with CSE, comparing instance reduction and time/space complexity with standard flattening, which outlines its scope. Second, we present how to increase the number of common subexpressions in a constraint model by reformulation and include a formal cost analysis. Third, we show how to lift the approach of flattening instances to whole problem classes, an alternative, novel approach to instancewise compilation. We formally integrate CSE into classwise flattening,and show when classwise compilation is preferable to
instancewise compilation. Finally, experiments confirm our theoretical findings and demonstrate the benefits of CSEbased flattening.
[1] A. Rendl, I. Miguel, I.P. Gent and C. Jefferson Enhancing
Constraint Model Instances during Tailoring In SARA,
2009, to appear

 Available as
PDF

2009/14
 T.G. Philbin, C. Xiong and U. Leonhardt 
 Casimir stress in an inhomogeneous medium


The Casimir effect in an inhomogeneous dielectric is investigated using Lifshitz's theory of electromagnetic
vacuum energy. A permittivity function that depends continuously on one Cartesian coordinate is chosen,
bounded on each side by homogeneous dielectrics. The result for the Casimir stress is infinite everywhere
inside the inhomogeneous region, a divergence that does not occur for piecewise homogeneous dielectrics
with planar boundaries. A Casimir force per unit volume can be extracted from the infinite stress but it
diverges on the boundaries between the inhomogeneous medium and the homogeneous dielectrics. An alternative regularization of the vacuum stress is considered that removes the contribution of the inhomogeneity
over small distances, where macroscopic electromagnetism is invalid. The alternative regularization yields
a finite Casimir stress inside the inhomogeneous region, but the stress and force per unit volume diverge
on the boundaries with the homogeneous dielectrics. The case of inhomogeneous dielectrics with planar
boundaries thus falls outside the current understanding of the Casimir effect.

 Available as
PDF

2009/13
 Christopher Jefferson, Neil Moore, Peter Nightingale and Karen Petrie 
 Implementing Logical Connectives in Constraint Programming


Combining constraints using logical connectives such as disjunction is ubiquitous in constraint programming, because it adds considerable expressive power to a constraint language. We explore the solver architecture needed to propagate such combinations of constraints efficiently. In particular we describe two new features (named satisfying sets and constraint trees) of the Minion solver. We also make use of watched literals, and with these three complementary features we are able to make considerable efficiency gains.
A key reason for the success of Boolean Satisfiability (SAT) solvers is their ability to propagate OR constraints efficiently, making use of watched literals. We successfully generalise this approach to an OR of an arbitrary set of constraints, maintaining the crucial property that at most two constraints are active at any time, and no computation at all is done on the others. An AND algorithm is also given, and may be embedded within the OR. Using this approach, we demonstrate speedups of over 10,000 times in some cases, compared to traditional constraint programming approaches. We also prove that the OR algorithm enforces generalized arc consistency (GAC) when all its child constraints have a GAC propagator, and no variables are shared between children. By extending the OR propagator, we present a propagator for AT LEAST K, which expresses that at least k of its child constraints are satisfied in any solution.
Some logical expressions (e.g. exclusiveor) cannot be compactly expressed using AND, OR and AT LEAST K. Therefore we investigate reiﬁcation of constraints. We present a fast generic algorithm for reification using satisfying sets and watched literals. In contrast to AND, OR and AT LE AS T K, reiﬁcation allows for any logical expression. We compare algorithms which use satisfying sets and watched literals with alternatives using static triggers, and again we demonstrate huge speedups.

 Available as
PDF

2009/12
 Andrea Rendl and Ian Miguel 
 Automated Constraint Model Enhancement during Tailoring


Constraint modelling is difficult, particularly for novices. Hence, automated methods for improving models are valuable. The context of this paper is tailoring, a process where a solverindependent constraint model is adapted to a target solver. Tailoring is augmented with automated enhancement techniques, in particular common subexpression detection and elimination, which, while powerful, can be performed inexpensively if applied selectively. Experimental results show very substantial improvements in search performance of tailored models.

 Available as
PDF

2009/11
 Fiona Brunk and Nik Ruskuc 
 Largest Intersecting Families of Almost Linear Posets


The publication of the ErdösKoRado Theorem in 1961 sparked an interest in classifying the largest intersecting sets of various combinatorial structures such as sets, words, permutations and graphs. In this paper we introduce the idea of intersecting posets: two posets on n points intersect if they share a comparison. It is easily seen that an intersecting set of linear orders on n points has size at most n!/2. Let Y_{k,n} be the set of all posets which can be obtained from a linear order on n points by removing the comparison between the k^{th} and k + 1^{st} smallest points. We show that an intersecting subset of Y_{k,n} has size at most n!/4 and classify the intersecting families attaining this bound. Moreover, we obtain a sharp bound on intersecting subsets of ∪ ^{n1}_{k=1}Y_{k,n}.

 Available as
PDF

2009/10
 Fiona Brunk and Sophie Huczynska 
 Some ErdösKoRado Theorems for Injections


This paper investigates tintersecting families of injections, where two injections a, b from [k] to [n] tintersect if there exists X ⊆ [k] with X ≥ t such that a(x) = b(x) for all x ∈ X. We prove that if F is a 1intersecting injection family of maximal size then all elements of F have a fixed image point in common. We show that when n is large in terms of k and t, the set of injections which fix the first t points is the only tintersecting injection family of maximal size, up to permutations of [k] and [n]. This is not the case for small n. Indeed, we prove that if k is large in terms of k  t and n  k, the largest tintersecting injection families are obtained from a process of saturation rather than fixing.

 Available as
PDF

2009/9
 Neil Moore and Ian Miguel 
 30th April 2009

 Learning Implied Constraints Lazily


Explanations are a technique for reasoning about constraint
propagation, which have been applied in many learning, backjumping
and user interaction algorithms. To date, explanations have been recorded
"eagerly" when the propagation happens, which leads to inefficient use
of time and space, because many will never be used. In this paper we
show that it is possible and highly effective to calculate explanations
retrospectively when they are needed. To this end, we implement "lazy"
explanations in a state of the art learning framework. Experimental results confirm the effectiveness of the technique: we achieve reduction in
the number of explanations calculated up to a factor of 200 and robust
reductions in overall solve time up to a factor of 2.

 Available as
PDF

2009/8
 WHB Wallace and Tom Kelsey 
 Human Ovarian Reserve from Conception to the Menopause


Current understanding is that the human ovary contains a fixed number of several million nongrowing follicles (NGF), established by five months of gestational age, that declines with increasing age to the menopause when approximately 1,000 NGF remain at an average age of 5051 years. With approximately 450 ovulatory monthly cycles in the normal human reproductive lifespan, this progressive decline in NGF numbers is attributed to follicle death by apoptosis. Individual histological studies have quantified NGF numbers over limited age ranges. However, no model describing the rate of establishment and decline of the NGF population from conception to menopause has been previously reported. Here we describe the best fitting model of the agerelated NGF population in the human ovary from conception to menopause. Our model matches the logadjusted NGF population to a fiveparameter asymmetric double Gaussian cumulative (ADC) curve (r2 = 0.81). Furthermore we found that the rate of NGF recruitment into growing follicles for all women increases from birth until approximately age 14 years (coinciding with puberty) then decreases towards the menopause. The explanation for this newfinding remains unclear but is likely to involve both paracrine and endocrine factors. We describe and analyse the best fitting model for the establishment and decline of human NGF; our model extends our current understanding of human ovarian reserve.

 Available as
PDF

2009/7
 Lars Kotthoff 
 Constraint solvers: An empirical evaluation of design decisions


This paper presents an evaluation of the design decisions made in four stateoftheart constraint solvers; Choco, ECLiPSe, Gecode, and Minion. To assess the impact of design decisions, instances of the five problem classes nQueens, Golomb Ruler, Magic Square, Social Golfers, and Balanced Incomplete Block Design are modelled and solved with each solver. The results of the experiments are not meant to give an indication of the performance of a solver, but rather investigate what influence the choice of algorithms and data structures has.
The analysis of the impact of the design decisions focuses on the different ways of memory management, behaviour with increasing problem size, and specialised algorithms for specific types of variables. It also brifly considers other, less significant decisions.

 Available as
PDF

2009/6
 Alan J. Cain, Graham Oliver, Nik Ruskuc and Richard M. Thomas 
 Automatic presentations and semigroup constructions


An automatic presentation for a relational structure is, informally, an abstract representation of the elements of that structure by means of a regular language such that the relations can all be recognized by finite automata. A structure admitting an automatic presentation is said to be FApresentable. This paper studies the interaction of automatic presentations and certain semigroup constructions, namely: direct products, free products,finite Rees index extensions and subsemigroups, strong semilattices of semigroups, Rees matrix semigroups, BruckReilly extensions, zerodirect unions, semidirect products, wreath products, ideals, and quotient semigroups. For each case, the closure of the class of FApresentable semigroups under that construction is considered, as is the question of whether the FApresentability of the semigroup obtained from such a construction implies the FApresentability of the original semigroup[s]. Classfications are also given of the FApresentable finitely generated Clifford semigroups, completely simple semigroups, and completely 0simple semigroups.

 Available as
PDF

2009/5
 Alan J. Cain, Graham Oliver, Nik Ruskuc and Richard M. Thomas 
 Automatic presentations for semigroups


This paper applies the concept of FApresentable structures to semigroups. We give a complete classification of the finitely generated FApresentable cancellative semigroups: namely, a finitely generated cancellative semigroup is FApresentable if and only if it is a subsemigroup of a virtually abelian group. We prove that all finitely generated commutative semigroups are FApresentable. We give a complete list of FApresentable onerelation semigroups and compare the classes of FApresentable semigroups and automatic semigroups.

 Available as
PDF

2009/4
 Ian P. Gent, Paul McKay, Ian Miguel, Peter Nightingale, and Sophie Huczynska 
 Modelling Equidistant Frequency Permutation Arrays in Constraints


Equidistant Frequency Permutation Arrays are combinatorial objects of interest in coding theory. A frequency permutation array is a type of constant composition code in which each symbol occurs the same number of times in each codeword. The problem is to find a set of codewords such that any pair of codewords are a given uniform Hamming distance apart. The equidistant case is of special interest given the result that any optimal constant composition code is equidistant. This paper presents, compares and combines a number of different constraint formulations of this problem class, including a new method of representing permutations with constraints. Using these constraint models, we are able to establish several new results, which are contributing directly to mathematical research in this area.

 Available as
PDF

2009/3
 Andrea Rendl, Ian Miguel, Ian P. Gent and Peter Gregory 
 Enhancing Constraint Models of Planning Problems by Common Subexpression Elimination


Constraint Programming is an attractive approach for solving AI planning problems by modelling them as Constraint Satisfaction Problems (CSPs). However, formulating effective constraint models of complex planning problems is challenging, and CSPs resulting from standard approaches often require further enhancement to perform well. Common subexpression elimination is a general technique for improving constraint models, which has been shown to lead to a great reduction in instance size, solving time and search space. This paper argues that models of AI planning problems are particularly amenable to this approach. We present four case studies to substantiate this argument, three of which include novel constraint models of AI planning problems. In each, we describe the constraint model, highlight the sources of common subexpressions, and present an empirical analysis of the effect of eliminating common subexpressions.

 Available as
PDF

2009/2
 Sophie Huczynska 
 Equidistant frequency permutation arrays and related constant composition codes


This paper introduces and studies the notion of an equidistant frequency
permutation array (EFPA). An EFPA of length n = mλ, distance d and size v
is defined to be a v x n array T such that 1) each row is a multipermutation on a
multiset of m symbols, each repeated with frequency λ, and 2) the Hamming
distance between any two distinct rows of T is precisely d. Such an array
generalizes the wellstudied equidistant permutation array: it corresponds to
a special kind of constant composition code (CCC). Bounds and constructions
are obtained for EFPAs and related CCCs (many optimal), and links with
other combinatorial structures are explored.

 Available as
PDF

2009/1
 Hannah J. Coutts, Martyn Quick and Colva M. RoneyDougal 
 The Primitive Permutation Groups of Degree Less than 4096


In this paper we use the Classification of the Finite Simple Groups, the O'NanScott Theorem and Aschbacher's theorem to classify the primitive permutation groups of degree less than 4096. The results will be added to the primitive groups databases of GAP and MAGMA.

 Available as
PDF

2008/14
 Andrea Rendl, Ian P. Gent and Ian Miguel 
 Eliminating Common Subexpressions During Flattening


Many constraint models contain common subexpressions. Eliminating this redundancy has two key benefits, both of which contribute to a substantial reduction in solving time: a dramatic reduction in the size of the model, and enhanced constraint propagation leading to reduced search. Depending on the facilities offered by a particular constraint solver, flattening is required to tailor solverindependent constraint models to a particular target solver. This paper shows how to exploit the flattening process to eliminate common subexpressions efficiently, similar to the process compilers perform when compiling source code. Experimental results demonstrate the utility of our approach.

 Available as
PDF

2008/13
 M. Rajkhowa, S. Brett, T. Kelsey, C. Lipina, L. Logie, D. J. Cuthbertson, J. Petrie and C. Sutherland 
 Altered Extracellular Regulated Kinase Signaling in skeletal muscle in women with Polycystic Ovary Syndrome


Polycystic ovary syndrome is the most common gynaecological endocrine disorder in women of reproductive age. Peripheral insulin resistance is a feature of the disorder, leading to compensatory hyperinsulinaemia which has a suggested role in the pathogenesis. Previous studies examining the mechanism of insulin resistance have suggested altered phosphorylation of insulin recetor substrate (IRS), and in the phosphotidylinositol (PI) 3 Kinase activity implicating that the metabolic pathway is altered while other studies suggesting an alteration in the mitogen activated Protein Kinase(MAPKinase) and Extracellular Regulated Kinase (ERK) signaling.
The aim of this study was to examine the insulinsignaling pathway in peripheral muscle to determine the possible site of insulin resistance in women with PCOS.

 Available as
PDF

2008/12
 M. Livie, S. Brett, T. Kelsey, K. Whalley, R. Hume, A. Burchell and M. Rajkhowa 
 A report on a two year experience in the recruitment of embryo donors for human stem cell derivation


The ethical derivation of human embryonic stem cell lines is critically dependent on the availability of donated embryos obtained with transparent, informed consent from couples undergoing assisted conception treatment. Spare embryos donated by these couples provide a valuable source for stem cell line generation, and has been supported by legislation and regulatory bodies in the UK.
The aim of this study was to report on a twoyear experience in recruiting couples undergoing fresh IVF/ICSI treatment for donation of their spare embryos for human embryonic stem cell derivation

 Available as
PDF

2008/11
 S. Brett, N. Bee, W. H. B. Wallace, M. Rajkhowa and T. W. Kelsey 
 Individual ovarian volumes obtained from 2D and 3D ultrasounds lack precision


Objective  To assess the precision of individual ovarian volume measurements by 2D and 3D transvaginal ultrasound scan.
Study Design  Transvaginal 2D and 3D ultrasound examinations were performed on 49 women attending a tertiary centre for investigation or treatment for subfertility. Two observers calculated ovarian volume, using both the prolate ellipsoid formula and virtual organ computeraided analysis (VOCAL), with rotation steps of 30 degrees (3D30).
Results  For the four comparisons (inter and intraobserver; 2D and 3D30) we obtained intraclass coefficients of 0.97 to 0.98; and standard errors ranging from 17% to 14% (for interobserver 2D and intraobserver 3D, respectively). The corresponding Coefficients of Repeatability ranged from 33% to 28%.
Conclusions  Measurement of transvaginal ovarian volumes using both 2D and 3D ultrasound is imprecise for individuals. The imprecision is greater for lower ovarian volumes, which may be important in clinical practice. The average of two or more measurements is likely to be more accurate than a single measurement.

 Available as
PDF

2008/10
 Ian P Gent, Ian Miguel and Peter Nightingale 
 Generalised Arc Consistency for the AllDifferent constraint: An Empirical Survey


The AllDifferent constraint is a crucial component of any constraint toolkit, language or solver, since it is very widely used in a variety of constraint models. The literature contains many different versions of this constraint, which trade strength of inference against computational cost. In this paper, we focus on the highest strength of inference, enforcing a property known as generalised arc consistency (GAC). This work is an analytical survey of optimizations of the main algorithm for GAC for the AllDifferent constraint. We evaluate empirically a number of key techniques from the literature. We also report important implementation details of those techniques, which have often not been described in published papers. We pay particular attention to improving incrementality by exploiting the stronglyconnected components discovered during the standard propagation process, since this has not been detailed before. Our empirical work represents by far the most extensive set of experiments on variants of GAC algorithms for AllDifferent. Overall, the best combination of optimizations gives a mean speedup of 168 times over the same implementation without the optimizations.

 Available as
PDF

2008/9
 Andreas Distler and Tom Kelsey 
 The Monoids of Orders Eight, Nine and Ten


We describe the use of symbolic algebraic computation allied with AI search techniques, applied to the problem of the identification, enumeration and storage of all monoids of order ten or less. Our approach is novel, using computer algebra to break symmetry and constraint satisfaction search to find candidate solutions. We present new results in algebraic combinatorics: up to isomorphism and antiisomorphism, there are 858,977 monoids of order eight; 1,844,075,697 monoids of order nine and 52,991,253,973,742 monoids of order ten.

 Available as
PDF

2008/8
 Steve Linton and John Bamberg 
 Some problems in finite geometry where computer investigations are important


One of the most famous applications of computers in finite geometry was the computer aided proof that there is no projective plane of order 10. To this date, it is still unknown whether every projective plane has order the power of a prime, or indeed, whether there exists a projective plane of order 12. The aforementioned computerproof caused much controversy in the early 1980's, along with other computer assisted proofs in mathematics which came forth at around that time. However, apart from the application that computers can have in proving theorems, they have had an ever increasing role in the search for geometric configurations. At around the same time as the "order 10" result, Andries Brouwer had been using the computer power available in the early 1980's to prove the nonexistence of ovoids in the Hermitian variety H(4, 4). The main protagonists of computer search in finite geometry have included Mathon, Moorehouse, Penttila and Royle, and their successes can be readily gleaned from the results in their literature. Moreover, there is an excellent survey on the role of computation in finite geometry by Penttila.

 Available as
PDF
 2008/7
 Peter Nightingale 
 Nonbinary Quantified CSP: Algorithms and Modelling


The Quantified Constraint Satisfaction Problem (QCSP) extends classical CSP in a way which allows reasoning about uncertainty. In this paper I present novel algorithms for solving QCSP. Firstly I present algorithms to perform constraint propagation on reified disjunction constraints of any length. The algorithms make full use of quantifier information to provide a strong consistency. Secondly I present a scheme to enforce the nonbinary pure value rule. This rule is capable of pruning universal variables.
Following this, two problems are modelled in nonbinary QCSP: the game of
Connect 4, and a variant of jobshop scheduling with uncertainty, in the form of machine faults. The job shop scheduling example incorporates probability bounding of scenarios (such that only fault scenarios above a probability threshold are considered) and optimization of the schedule makespan. These contribute to the art of modelling in QCSP, and are a proof of concept for applying QCSP methods
to complex, realistic problems. Both models make use of the reified disjunction
constraint, and the nonbinary pure value rule. The example problems are used
to evaluate the QCSP algorithms presented in this paper, identifying strengths and weaknesses, and to compare them to other approaches.

 Available as
PDF

2008/6
 Ian P Gent, Ian Miguel, and Peter Nightingale 
 The AllDifferent Constraint: Exploiting StronglyConnected Components and Other Efficiency Measures

 The AllDifferent constraint is a crucial component of any constraint toolkit, language or solver, since it is very widely used in a variety of constraint models. The literature contains many different versions of this constraint, which trade strength of inference against computational cost. In this paper, we focus on the highest strength of inference (enforcing a property known as generalised arc consistency  GAC), and propose several new variants of the AllDifferent constraint propagation algorithm that achieve this. Most importantly, we improve incrementality by exploiting the stronglyconnected components discovered during the standard propagation process, and improve efficiency by triggering the propagation process less often. We perform an extensive empirical evaluation of the new variants of AllDifferent versus existing GAC algorithms, as well as a fast AllDifferent algorithm that does less propagation. The results confirm the value of our new variants, which can improve runtimes over the stateoftheart by over five times.
REPLACED BY 2008/9

 Available as
PDF

2008/5
 Andreas Distler, and Tom Kelsey 
 The Monoids of Order Eight and Nine

 We describe the use of symbolic algebraic computation allied
with AI search techniques, applied to the problem of the identification,
enumeration and storage of all monoids of order 9 or less. Our approach
is novel, using computer algebra to break symmetry and constraint sat
isfaction search to find candidate solutions. We present new results in
algebraic combinatorics: up to isomorphism and antiisomorphism, there
are 858,977 monoids of order 8 and 1,844,075,697 monoids of order 9.

 Available as
PDF

2008/4
 George Havas, Edmund F Robertson and Dale C Sutherland 
 Behind and Beyond a Theorem on Groups Related to Trivalent Graphs

 In 2006 we completed the proof of a fivepart conjecture which was made in 1977 about a family of groups related to trivalent graphs. This family covers all 2generator, 2relator groups where one relator specifies that a generator is an involution and the other relator has three syllables. Our proof relies upon detailed but general computations in the groups under question. The proof is theoretical, but based upon explicit proofs produced by machine for individual cases. Here we explain how we derived the general proofs from specific cases. The conjecture essentially addressed only the finite groups in the family. Here we extend the results to infinite groups, effectively determining when members of this family of finitely presented groups are simply isomorphic to a specific quotient.

 Available as
PDF

2008/3
 Max Neunhöffer, and Cheryl E Praeger 
 Computing Minimal Polynomials of Matrices

 We present and analyse a MonteCarlo algorithm to compute the minimal polynomial of an n × n matrix over a finite
field that requires O(n3 ) field operations and O(n) random
vectors, and is well suited for successful practical implementa
tion. The algorithm, and its complexity analysis, use standard
algorithms for polynomial and matrix operations. We compare
features of the algorithm with several other algorithms in the
literature. In addition we present a deterministic verification
procedure which is similarly efficient in most cases but has a
worstcase complexity of O(n4 ). Finally, we report the results
of practical experiments with an implementation of our algo
rithms in comparison with the current algorithms in the GAP
library.

 Available as
PDF

2008/2
 Neil Moore, and Patrick Prosser 
 The Ultrametric Constraint and its Application to Phylogenetics

 A phylogenetic tree shows the evolutionary relationships among existing species. Internal nodes of the tree represent speciation events and leaf nodes correspond to existing species. A goals of phylogenetics is to combine such trees into larger trees, called supertrees, whilst respecting the relationships in the original trees. A rooted tree exhibits an ultrametric property; that is, for any three leaves of the tree it must be that one pair has a deeper most recent common ancestor than the other pairs, or that all three have the same most recent common ancestor. This inspires a constraint programming encoding for rooted trees. We present an efficient constraint that enforces the ultrametric property over a symmetric array of constrained integer variables, with the inevitable property that the lower bounds of any three variables are mutually supportive. We show that this allows an efficient constraintbased solution to the supertree construction problem, an important problem in phylogenetics. We demonstrate that the versatility of constraint programming can be exploited to allow solutions to variants of the supertree construction problems.

 Available as
PDF

2008/1
 Andy Grayland, Chris Jefferson, Ian Miguel, and Colva RoneyDougal 
 Minimal Ordering Constraints for some Families of Variable Symmetries

 Variable symmetries in a constraint satisfaction problem can
be broken by adding lexicographic ordering constraints. Existing general
methods of generating such sets of ordering constraints can require a
huge number of constraints. This adds an unacceptable overhead to the
solving process. Methods also exist by which this large set of ordering
constraints can be reduced to a much smaller set automatically, but
their application is also prohibitively costly. In contrast, this paper takes
a bottomup approach. It examines some commonlyoccurring families
of groups and derives a minimal set of ordering constraints sufficient
to break the symmetry each group describes. These minimal sets are
then used as building blocks to generate minimal sets of ordering constraints for groups constructed via direct and imprimitive wreath products. Experimental results confirm the value of minimal sets of ordering
constraints, which can now be generated much more cheaply than with
previous methods.

 Available as
PDF

2007/14
 S. Brett, T. W. Kelsey, W. H. B. Wallace and M. Rajkhowa 
 Does 3D ultrasound measurement improve the assessment of ovarian volume?

 Measurement of ovarian volume has been used to screen women before in vitro fertilisation (IVF) treatment as an indirect indicator of ovarian reserve. Currently, access to 2D ultrasound scanning is more widely available and the majority of studies relating ovarian volume measurements to IVF outcome have been performed using 2D scanning.
The aim of this study is to compare validity, reliability and precision of ovarian volume measurements by 2D and 3D transvaginal ultrasound scan. We have used the data to construct precision charts which give welldefined limits for the true volume when an estimated volume has been obtained by either method.

 Available as
PDF

2007/13
 Steve Linton and Alexander Konovalov 
 Symbolic Computation Software Composability Protocol (SCSCP) Specification Version 1.0

 Modern symbolic computations increasingly require combinations of capabilities available in several different systems. Moreover, there are increasing numbers of symbolic computation resources, such as databases or specialized software which may constitute an interest as Web services accessible over the Internet. This specification describes the OpenMathbased Symbolic Computation Software Composibility Protocol by which a computer algebra system may offer services and a client may employ them.

 Available as
PDF

2007/12
 M. H. Albert and S. A. Linton 
 Growing at a Perfect Speed

 A collection of permutation classes is exhibited whose growth rates form a perfect set, thereby refuting some conjectures of Balogh, Bollobás and Morris.

 Available as
PDF and
Postscript

2007/11
 J. Araújo, P. V. Bünau and J. D. Mitchell 
 Computing Automorphisms of Semigroups

 In this paper an algorithm is presented that can be used to calculate the automorphism group of a finite transformation semigroup. The general algorithm employs a special method to compute the automorphism group of a finite simple semigroup. As an application of the algorithm, all the automorphism groups of semigroup of order at most 7 and of the multiplicative semigroups of some group rings are found. We also consider the question of which groups occur as automorphism groups of semigroups of several distinguished types.

 Available as
PDF

2007/10
 Volodymyr Mazorchuk and Victor Maltcev 
 Presentation of the singular part of the Brauer monoid

 We obtain a presentation for the singular part of the Brauer monoid with respect to an irreducible system of generators, consisting of idempotents. As an application of this result we get a new construction of the symmetric group via connected sequences of subsets. Another application describes the lengths of elements in the singular part of the Brauer monoid with respect to the system of generators, mentioned above.

 Available as
PDF

2007/9
 Ganna Kudryavtseva and Victor Maltcev 
 Presentation for the Partial Dual Inverse Symmetric Monoid

 We give a monoid presentation in terms of generators and defining relationships for the partial analogue of the finite dual inverse symmetric monoid.

 Available as
PDF

2007/8
 Victor Maltcev 
 On a New Approach to the Dual Symmetric Inverse Monoid I*_{X}

 We construct the inverse partition semigroup IP_{x}, isomorphic to the dual symmetric inverse monoid I*_{x }, introduced in [6]. We give a convenient geometric illustration for elements of IP_{x }. We describe all maximal semigroups of IP_{x } and find a generating set for IP_{x } when X is finite. We prove that all the automorphisms of IP_{x} are inner. We show how to embed the symmetric inverse semigroup into the inverse partition one. For finite sets X, we establish that, up to equivalence, there is a unique faithful effective transitive representation of IP_{n} , namely to IS_{2n2 }. Finally, we construct an interesting Hcrosssection if IP_{n }, which is reminiscent of IO_{n }, the Hcrosssection of IS_{n }, constructed in [4].

 Available as
PDF

2007/7
 Victor Bovdi, Eric Jespers, Alexander Konovalov 
 Torsion units in integral group rings of Janko simple groups

 Using the LutharPassi method, we investigate the classical Zassenhaus conjecture for the normalized unit group of integral group rings of Janko simple groups. As a consequence, for the Janko simple groups J1, J2 and J3 we confirm Kimmerle's conjecture on prime graphs.

 Available as
PDF

2007/6
 Tom Kelsey 
 The Automated Calculation of Human Ovarian Reserve

 We report on the use of AI techniques  including image analysis, feature recognition, machine learning and constraint satisfaction  applied to the problem of determining the population of primodial follicles in a human ovary. We highlight the importance of accurate population data for studies that aim to predict the age of menopause in healthy women, and for studies that quntify damage to ovarian tissue as a result of radio or chemotherapy. We describe existing methods used to estimate primordial, and review the strenghts and weaknessesof these approaches. We present a novel methodology for counting each and every primordial follicle in an ovary, together with details of our implementation and empirical evaluation.

 Available as
PDF

2007/5
 Steve Linton and Alexander Konovalov 
 Symbolic Computation Software Composability Protocol (Also Known as Protocol X) Specification

 REPLACED BY PREPRINT 2007/13.

 Available as
PDF

2007/4
 Ian P. Gent, Tom Kelsey, Steve Linton, Justin Pearson and Colva M. RoneyDougal 
 Groupoids and Conditional Symmetry

 We introduce groupoids  generalisations of groups in which not all pairs of elements may be multiplied, or, equivalently, categories in which all morphisms are invertible  as the appropriate algebraic structures for dealing with conditional symmetries in Constraint Satisfaction Problems (CSP's). We formally define the Full Conditional Symmetry Groupoid associated with any CSP, giving bounds for the number of elements that this groupoid can contain. We describe conditions under which a Conditional Symmetry subGroupoid forms a group, and, for this case, present an algorithm for breaking all conditional symmetries that arise at a search node. Our algorithm is polynomialtime when there is a corresponding algorithm for the type of group involved. We prove that our algorithm is both sound and complete  neither gaining nor losing solutions. We report on an implementation of the algorithm.

 Available as
PDF

2007/3
 Alexander Konovalov 
 Wreath Products in Modular Group Algebras of some Finite 2Groups

 Let K be field of characteristic 2 and let G be a finite nonabelian 2group with the cyclic derived subgroup G', and there exists a central element z of order 2 in Z(G)G'. We prove that the unit group of the group algebra KG possesses a section isomorphic to the wreath product of a group of order 2 with the derived subgroup of the group G, giving for such groups a positive answer to the question of A. Shalev.

 Available as
PDF

2007/2
 Victor Bovdi, Alexander Konovalov and Steve Linton 
 Torsion Units in Integral Group Ring of the Mathieu Simple Group M_{22}

 We investigate the possible torsion units of the normalised unitgroup of the integral group ring of Mathieu sporadic group M_{22}. We confirm the Kimmerle conjecture on prime graphs for this group and dramatically restrict the possibilities for a counter example to the stronger Zassenhaus conjecture.

 Available as
PDF

2007/1
 Tom Kelsey 
 Efectos de la Radioterapia Sobre el Ovario y el Útero

 En este trabajo u investigación describimos los efectos cuantitativos de una dosis fraccionada de la radioterapia al ovario. Calculamos la dosis requeria para matar al 50% de una población (LD_{50}) del oocyte humano, y utilizamos esto para predecir ambos edad en la falla ovárica, y la dosis efectiva para la esterilización. Describimos el método de WallaceKelsey para usar el volumen ovárico a predecimos más exactamente la falla ovárica para los individuos. Concluimos dando los efectos cualitativos de la radioterapia en el útero.

 Available as
PDF

2006/18
 Ian P. Gent , Chris Jefferson, Ian Miguel, and Peter Nightingale 
 Data Structures for Generalised Arc Consistency for Extensional Constraints

 Extensional (table) constraints are an important tool for attacking combinatorial problems with constraint programming. Recently there has been renewed interest in fast propagatoin of algorithms for these constraints. We describe the use of two alternative data structures for maintaining generalised arc consistency on extensional constraints. The first, the NextDifference list, is novel and has been developed with this application in mind. The second, the trie, is well known but it's use in this context is novel. Empirical analyses demonstrate the efficiency of the resulting approaches, both in GACschema, and in the watchedliteral table constraint in Minion.

 Available as
PDF

2006/17

Björn Assmann and Steve Linton 
 Using the Mal'cev correspondence for collection in polycyclic groups

 We describe several approaches for realising the Mal'cev correspondence between Qpowered nilpotent groups and nilpotent Lie algebras over Q. We apply it to fast collection in polycyclic groups. Our methods are fully implemented and publicly available. We report on the implementation and give runtimes for some example groups.

 Available as:
PDF

2006/16
 Ian P. Gent , Warwick Harvey, Tom Kelsey , Steve Linton and Karen Petrie 
 Groups and Constraints:Symmetry Breaking During Search and Symmetry Breaking by Dominance Detection

 In this paper we define, describe and analyse dynamic techniques for breaking symmetries in constraint satisfaction problems. The techniques, symmetrybreaking during search and symmetrybreaking by dominance detection, are sound  no solutions are lost  and complete  exactly one member of each symmetry equivalent class of solutions will be returned, subject to the correct permutation group being identified before search. Our implementations use advanced computational group theory algorithms to answer symmetryrelated questions during search. We demonstrate that the cost of computing answers to these questions is often considerably outweighed by the resulting pruning of search in an NPcomplete class of problems. We compare our methods with each other, and with other related symmetrybreaking paradigms.

 Available as:
PDF

2006/15
 Chris Jefferson, Tom Kelsey, Steve Linton and Karen Petrie 
 GAPLex: Generalised Static Symmetry Breaking

 Chapter 1 of "Future and trends of Constraint Programming", Frederic Benhamou, Narendra Jussien and Barry O'Sullivan, December 2006.

 Available as:
PDF

2006/14
 Björn Assmann, and Bettina Eick 
 Testing polycyclicity of finitely generated rational matrix groups

 We describe algorithms for testing polycyclicity and nilpotency for finitely generated subgroups of GL(d, Q) and thus we show that these properties are decidable. Variations of our algorithm can be used for testing virtual polycyclicity and virtual nilpotency for finitely generated subgroups of GL(d, Q).

 Available as:
PDF

2006/13
 Ian P. Gent, Chris Jefferson, Tom Kelsey, Inês Lynce, Ian Miguel, Peter Nightingale, Barbara M. Smith, and S. Armagan Tarim 
 Search in the Patience Game 'Black Hole'

 We present an evaluation of different AI search paradigms applied to a natural planning problem. The problem we investigate is a particular card game for one player called Black Hole. For paradigms such as SAT and Constraint Programming, the game has the particular advantage that all solutions are the same length. We show that a general version of Black Hole is NPcomplete. Then we report on the application of a number of AI paradigms to the problem, namely Planning, Constraint Programming, SAT, MixedInteger Programming and a specialised solver. An important feature of Black Hole is the presence of symmetries which arise during the search process. We show that tackling these can improve search dramatically, as can caching states that occur during search. Our implementations as SAT, Constraint Programming and Planning problems are efficient and competitive, allowing detailed empirical evaluation of the strengths and weaknesses of each methodology. Our empirical evaluation shows that Black Hole is winnable approximately 87% of the time, and that given instances can be trivially solved, easy to solve, hard to solve and even intractable, depending on the AI methodology used to obtain solutions.

 Available as:
PDF

2006/12
 Colin M. Campbell, George Havas, Colin Ramsay and Edmund F. Robertson 
 On the efficiency of the simple groups with order less than a million and their covers

 There is much interest in finding short presentations for the finite simple groups. In a previous paper we produced nice efficient presentations for all small simple groups and for their covering groups. Here we extend those results from simple group order less than 100,000 up to order one million, but we leave one simple group and one covering group for which the efficiency question remains unresolved. We give presentations that are better than available before, in terms of length and in terms of computational properties, in the process answering two previously unresolved problems about the efficiency of covering groups of simple groups. Our results are based on major amounts of computation. We make substantial use of systems for computational group theory and, in particular, of computer implementations of coset enumeration.

 Available as:
PDF

2006/11
 C.M. Campbell and P.P. Campbell 
 Search techniques, Fibonacci lengths and centropolyhedral groups

 For a finitely generated group G=(A) where A={a_{1}, a_{2},..., a_{n}} the sequence x_{i}=a_{i+1}, 0 ≤ i ≤ n1, x_{i+n}= ∏ ^{n}_{j=1} x_{i+j1}, i ≥ 0, is called the Fibonacci orbit of G with respect to the generating set A, denoted F_{A}(G). If F_{A}(G) is periodic, we call the length of the period of the sequence the Fibonacci length of G with respect to A, written LEN_{A}(G). We examine the Fibonacci engths of all generating pairs for certain centropolyhedral groups. The problem requires a variety of approaches both exhaustive and random search.

 Available as:
PostScript and
PDF

2006/10
 Colin M. Campbell, George Havas and Edmund F Robertson 
 Addendum to An Elementary Introduction to Coset Table Methods in Computational Group Theory

 Available as:
PostScript and
PDF

2006/9
 Elizabeth H. Kimber, John J. O'Connor and Edmund F Robertson 
 Cyclic Minimal Generating Sets for Abelian Groups

 A finite group is said to be cyclically generated if it has an
automorphism that cycles through a generating set for the group. Such
a set will be called a cyclic generating set. We show that every finite
abelian group is cyclically generated, and then present results concerning
the existence of cyclic minimal generating sets for finite abelian groups
of ranks 3, 4, and 5. Further results about cyclic generating sets of prime
or squarefree size are also included.

 Available as:
PostScript and
PDF

2006/8
 John R. Britnell, Anton Evseev, Robert M. Guralnick, Petra E. Holmes and Attila Maróti 
 Sets of elements that pairwise generate a linear group

 Let G be any of the groups (P )GL(n, q), (P )SL(n, q). Define a (simple) graph Γ = Γ(G) on the set of elements of G by connecting two vertices by an edge if and only if they generate G. We prove that if the dimension n is at least 12 and not congruent to 2 modulo 4, then the maximum size of a complete subgraph in Γ is equal to the chromatic number of Γ. This work was motivated by a question of Blackburn.

 Available as:
PDF

2006/7
 Petra E. Holmes and Attila Maróti 
 Covering and generating sporadic simple groups

 For a noncyclic finite group G that can be generated by two elements let σ(G) be the least integer k so that G is the union of k of its proper subgroups, and let µ(G) be the largest integer m so that there exists a subset X of G of size m with the property that any two distinct elements of X generate G. Clearly µ(G) ≤ σ(G). In this paper we prove that σ(G) ≤ 4 ⋅ µ(G) for a sporadic simple group G.

 Available as:
PDF

2006/6
 J. D. Bradley and P. E. Holmes 
 Improved Bounds for the spread of sporadic groups

 The spread of a group G is the greatest number r such that, for every set of nontrivial elements {x_{1}, . . . , x_{r}}, there exists an element y with the property that {x_{i}, y} = G for 1 ≤ i ≤ r. In this paper we obtain good upper bounds for the spread of 14 sporadic simple groups computationally and determine the value of the spread of M_{11} by hand.

 Available as:
PDF

2006/5
 Ulf Leonhardt 
 Notes on Conformal Invisibility Devices

 As a consequence of the wave nature of light, invisibility devices based on isotropic media cannot be perfect. The principal distortions of invisibility are due to reflections and time delays. Reflections can be made exponentially small for devices that are large in comparison with the wavelength of light. Time delays are unavoidable and will result in wavefront dislocations. Thispaper considers invisibility devices based on optical conformal mapping. The paper shows that the time delays do not depend on the directions and impact parameters of incident light rays, although the refractiveindex profile of any conformal invisibility device is necessarily asymmetric. The distortions of images are thus uniform, which reduces the risk of detection. The paper also shows how the ideas of invisibility devices are connected to the transmutation of force, the stereographic projection and Escheresque tilings of the plane.

 Available as:
PDF

2006/4
 Ulf Leonhardt 
 Optical Conformity Mapping

 An invisibility device should guide light around an object as if nothing were there, regardless of where the light comes from. Ideal invisibility devices are impossible, owing to the wave nature of light. This study develops a general recipe for the design of media that create perfect invisibility within the accuracy of geometrical optics. The imperfections of invisibility can be made arbitrarily small to hide objects that are much larger than the wavelength. With the use of modern metamaterials, practical demonstrations of such devices may be possible. The method developed here can also be applied to escape detection by other electromagnetic waves or sound.

 Available as:
PDF

2006/3
 Ian Gent, Ian Miguel, and Peter Nightingale 
 Data Structures for Generalised Arc Consistency for Extensional Constraints

 We describe the use of two alternative data structures for maintaining generalised arc consistency on table/extensional constraints. The first, the NextDifference list, is novel and has been developed with this application in mind. The second, the trie, is well known but its use in this context is novel. Empirical analyses demonstrate the efficiency of the resulting approaches.

 Available as:
PDF

2006/2
 Chris Jefferson, Tom Kelsey, Steve Linton and Karen Petrie. 
 GAPLex: Combining Static and Dynamic Symmetry Breaking

 We describe a novel and effective suite of algorithms that combine the efficiency and ease of use of lexordering, with the power of
breaking symmetry in CSPs by using computational group theory during search. We show that our new symmetry breaking method, GAPLex,
is sound (will neither lose solutions nor return incorrect solutions) and
complete (will return exactly one member from each class of symmetrically equivalent solutions). We demonstrate that our implementation of
GAPLex is competitive with other methods, being effectively applicable
to CSPs with large domains and less than full variable and/or value symmetry. We also describe how a variation of GAPLex can be combined
with incomplete symmetry breaking methods  such as doublelex  to
provide fast and complete symmetry breaking. We believe this to be the
first method that successfully combines the posting of symmetry breaking
constraints before search, with symmetry breaking by analysis of search
states. We provide empirical evidence that our implementation can be
more effective than using either the posting of constraints before search
or the analysis of searchstate in isolation.

 Available as:
PostScript and
PDF

2006/1
 Goulnara Arzhantseva, Pierre de la Harpe and Delaram Kahrobaei. 
 The true prosoluble completion of a group: examples and open problems


The true prosoluble completion PS (&Gamma) of a group &Gamma is the inverse limit of the projective system of soluble quotients of &Gamma . Our purpose is to describe examples and to point out some natural open problems. We answer the analogue of a question of Grothendieck for profinite completions by providing examples of pairs of nonisomorphic residually soluble groups with isomorphic true prosoluble completions. We also provide a new class of finitely generated examples which answer the original Grothendieck's problem.

 Available as:
PostScript and
PDF

2005/6
 James D Mitchell ,
Yann Peresse and Martyn Quick. 
 Generating Sequences of Functions


In 1934 Sierpinski proved that every function from a countable family X
of continuous functions f : [0, 1] > [0, 1] can be obtained as a composition of four such functions. These four functions are said to generate the aforementioned family. The sequence X is not necessarily closed under composition, so it may be more precise to say that these four functions generate a semigroup containing X. The difference being minor, we allow ourselves this abuse of notation. The purpose of this paper is to find the least number of functions from a family F that generate any given sequence of functions from F. The families considered are continuous, Bairen, Lesbegue or Borel measurable, increasing or differentiable functions from the closed unit interval [0, 1] to itself and increasing functions from the natural numbers N to N.
In Theorem 2.1 we prove, using elementary arguments, that it is possible to generate any countable family of continuous functions using just two such functions. Finding two continuous functions which cannot be generated by one continuous
function is not difficult. The argument used for continuous functions is modified to show the analogues for Bairen functions and Lebesgue measurable functions in Theorems 2.4 and 2.5, respectively. With three examples of families of functions with this property, it is reasonable to ask for an example where the number of functions required is not 2. Theorem 3.1 demonstrates that every function from a countable family of increasing functions on the closed unit interval can be generated by three, but not necessarily two, such functions. On the other hand, there exists a countable family of increasing functions on the natural numbers that is not generated by any finite number of such functions: see Theorem 4.1. Finally, in Theorem 4.2 a countable sequence of infinitely many times differentiable functions is given that is not generated by any finite number of differentiable functions.

 Available as:
PostScript and
PDF

2005/5
 George Havas ,
Edmund F Robertson and Dale C Sutherland. 
 The F^{a,b,c} conjecture is true, II


In 1977 a fivepart conjecture was made about a family of groups related to trivalent graphs and subsequently two parts of the conjecture have been proved. The conjecture completely determines all finite members of the family. Here we complete the proof of the conjecture by giving proofs for the remaining three parts.

 Available as:
PostScript and
PDF

2005/4
 Steve Linton and
Colva M RoneyDougal. 
 Identifying geometries preserved by matrix groups


In this article we show that given a matrix group G of low dimensions over a finite field, there exists at least one Aschbacher class containing G for which one can find all of the corresponding geometries that are preserved by G. For several Aschbacher classes we prove that one can find all ways in which G is a member of that class, irrespective of whether G is a member of another class.

 Available as:
PostScript and
PDF

2005/3
 George Havas and
Edmund F Robertson. 
 The F^{a,b,c} conjecture is true, I


In 1977 a fivepart conjecture was made about a family of groups related to trivalent graphs and one part of the conjecture was proved. The conjecture completely determines all finite members of the family. Here we prove another part of the conjecture and foreshadow a paper which completes the proof of the other three parts.

 Available as:
PostScript and
PDF

2005/2
 Björn Assmann

 Algorithmic use of the Mal'cev correspondence

 Mal'cev showed in the 1950s that there is a correspondence between radicable torsionfree nilpotent groups and rational nilpotent Lie algebras.
In this paper we show how to establish the connection between
the radicable hull of a finitely generated torsionfree nilpotent group
and its corresponding Lie algebra algorithmically.
We apply it to fast multiplication of elements of
polycyclically presented groups.


Available
as: PostScript and
PDF

2005/1

Martyn Quick

 Groups whose proper quotients are virtually abelian

 The just non(virtually abelian) groups with nontrivial
Fitting subgroup are classified. Particular attention is given to those
which are virtually nilpotent and examples are given of the interesting
phenomena that can occur.


Available
as: PostScript and
PDF

2004/13

Murray Elder

 Pattern avoiding permutations are contextsensitive


We establish a bijection from the set of all permutations (of a given length) that avoid a pattern q and a contextsensitive language


Available
as PostScript
and as PDF.

2004/12

Colva M. RoneyDougal

 The primitive groups of degree less than 2500


In this paper we use the O'NanScott Theorem and Aschbacher's theorem
to classify the primitive permutation groups of degree less than
2500.


Available
as PostScript
and as PDF. A subsidiary file of
tables is
available as Postscript and
as PDF

2004/11

Sophie Huczynska and
Nik Ruskuc

 Pattern classes of permutations via bijections between
linearly ordered sets.


A pattern class is a set of permutations closed
under pattern involvement or, equivalently, defined by certain
subsequence avoidance conditions. Any pattern class X which is
atomic, i.e. indecomposable as a union of proper subclasses, has a
representation as the set of subpermutations of a bijection
between two countable (or finite) linearly ordered sets A and
B. Concentrating on the situation where A is arbitrary and
B=N, we demonstrate how the ordertheoretic properties
of A determine the structure of X and we establish results
about independence, contiguousness and subrepresentations for
classes admitting multiple representations of this form.


Available as
PostScript
and as PDF

2004/10

Peter P. Campbell

 Wall numbers for the first 100,001 prime numbers


The file contains Wall numbers for the first 100,001 primes.
They are presented in a GAP readable list called wall_numbers that
contains 100,000 sublists of the form [ prime p, wall number of that
prime k(p), the number n such that 2(p(1)^n)/n=k(p)].


Available as
gzipped txt

2004/9

Martyn Quick

 Maximal complements in finite groups


Let G be a finite group with a nonabelian minimal normal
subgroup N which is a direct product of the simple group X. The
maximal subgroups of G which complement N and their conjugacy
classes are parametrised in terms of certain homomorphisms taking
values in Aut X and satisfying particular conditions.


Available as
PostScript
and as PDF

2004/8

Colin M. Campbell
and
Peter P. Campbell,

 The Fibonacci lengths of binary polyhedral groups and
related groups


In this paper we examine the behaviour of the Fibonacci
length of the
finite polyhedral groups, binary polyhedral groups and
related groups.


Available as
PostScript
and as PDF

2004/7

Peter Brooksbank,
Hongxun Qin,
Edmund Robertson,
and Akos Seress

 On Dowling Geometries of Infinite Groups


A finite subgeometry of a Dowling geometry for an infinite group is exhibited,
which cannot be embedded in a Dowling geometry for any finite group;
this provides a negative answer to a question of Bonin. 

Available as
PostScript
and as PDF

2004/6

Tom Kelsey,
Steve Linton,
and
Colva M. RoneyDougal

 New developments in symmetry breaking in search
using computational group theory


Symmetrybreaking in constraint satisfaction problems (CSPs) is a
wellestablished area of AI research which has recently developed
strong interactions with symbolic computation, in the form of computational
group theory. GEtrees are a new conceptual abstraction, providing
lowdegree polynomial time methods for breaking value symmetries in
CSPs. In this paper we analyse the structure of symmetry groups of
CSPs, and implement several combinations of GEtrees and the classical
SBDD method for breaking all symmetries. We prove the efficacy of our
techniques, and present preliminary experimental evidence of their
practical efficiency.


Available as
PostScript
and as PDF

2004/5

Derek F. Holt
and
Colva M. RoneyDougal

 Constructing maximal subgroups of classical groups


In this paper we show how to construct the maximal subgroups of the
finite classical groups of linear, symplectic or unitary type
in lowdegree polynomial time.


Available
as PostScript
and as PDF

2004/4
 Steve
Linton 
 Finding the smallest image of a set

 We describe an algorithm for finding a canonical image of
a set of points under the action of a permutation group. Specifically if
we order images by sorting them and ordering the resulting sequences
lexicographically, we find the first image. This has applications to
combinatorial and other search problems, allowing isomorphic results to
be eliminated more efficiently.
We give worstcase asymptotic running time estimates and practical results obtained with a
GAP implementation.

 Available as
PostScript
and as PDF

2004/3
 Colva M.
RoneyDougal,
Ian Gent,
Tom Kelsey, and
Steve Linton

 Tractable symmetry breaking using restricted search
trees


We present a new conceptual abstraction in symmetry breaking  the
GEtree. The construction and traversal of a GEtree breaks all
symmetries in any constraint satisfaction or similar problem.
We give a polynomialtime algorithm for this construction in the case of
CSPs with arbitrary value symmetries. We have implemented this
technique, and supply experimental evidence of its practical effectiveness.


Available as
PostScript
and as PDF

2004/2
 Colva M.
RoneyDougal 
 Conjugacy of subgroups of the general linear group

 In this paper we present a new, practical
algorithm for solving the subgroup
conjugacy problem in the general linear group. 

Available as
PostScript
and as PDF

2004/1
 Colin M. Campbell,
George Havas,
Colin Ramsay, and
Edmund F. Robertson

 Nice Efficient presentations for all small simple groups
and their covers


Prior to this paper all small simple groups were known to be efficient
but the status of four of their covering groups was unknown. We produce
nice efficient presentations for all of these groups, resolving the
previously unknown cases. We give presentations that are better than
available before in terms of length and in terms of computational
properties. In many cases our presentations have minimal possible length.
Our results are based on major amounts of computation. We make substantial
use of systems for computational group theory and, in particular, of
computer implementations of coset enumeration. To assist in reducing the
number of relators we provide theorems which enable the amalgamation of
power relations in certain presentations. We conclude with a selection
of unsolved problems about efficient presentations for simple groups
and their covers. 

Available as
PostScript
and as PDF

2003/4
 Colin M. Campbell and
Peter P. Campbell 
 On the minimal length of semigroup presentations

 We define the length of a
semigroup presentation and related ideas. Theoretical results and
bounds are presented, gained while investigating the lengths of groups
defined by semigroup presentations. Minimal length semigroup
presentations are obtained in certain cases. 

Available as
PostScript
and as PDF

2003/3

David C. Banks
and
Steve Linton

 Counting Cases in Marching Cubes: Toward a Generic Algorithm for
Producing Substitopes


This paper describes a technique for counting the cases that arise
in a family of visualization techniques. This family includes Marching
Cubes, Sweeping Simplices, Contour Meshing, Interval Volumes, and
Separating Surfaces. 

Available as
PostScript
and as PDF

2003/2

Alexander Hulpke
and
Steve Linton

 Total ordering on subgroups and cosets


We show how to compute efficiently a lexicographic ordering for subgroups and
cosets of permutation groups and, more generally, of finite groups with a
faithful permutation representation.

 Available as
PostScript
and as PDF

2003/1
 Ian Gent, Warwick Harvey,
Tom Kelsey and
Steve Linton

 Generic SBDD using GAP and ECLiPSe

 We introduce a generic implementation of symmetry
breaking by dominance
detection. The implementation uses ECLiPSe to model and constrain a
constraint satisfaction problem. Binary backtrack search with propagation
is also performed in ECLiPSe, together with a check for a dominating
group element at nodes in the search tree. These checks are performed in
the GAP computational group theory system, which runs as a subprocess
of ECLiPSe.
The results of the dominance checks are used to restrict search to parts
of the tree which are not symmetrically equivalent to a previously
searched section. A constraint logic programming practitioner using the
interface does not need to implement a dominance check for the problem;
given a small number (typically 26) of generating symmetries, the GAP
subprocess constructs a symmetry group, performs search for dominating
elements when required, and provides the ECLiPSe superprocess with the
information needed to restrict search.
Our implementation is deterministic: all nondominated nodes are visited
during search, and each dominance check either succeeds or fails in
finite time, so that only nonsymmetric solutions are returned. The
implementation easily handles problems involving
10^{23} symmetries, with only four permutations
needed to direct the dominance checks during search.

 Available as
PostScript
and as PDF

2002/7
 Colin M. Campbell,
Peter P. Campbell,
B. T. K. Hopson and
Edmund F. Robertson

 On the efficiency of direct powers of PGL(2,p)

 The paper proves the efficiency of direct powers of the
group G(p) given
by the presentation < a , b 
a ^{2} ,
b ^{p} ,
(ab ^{2})^{4} ,
(abab ^{2})^{3} >.
Depending on properties of the
prime p, the
group
G(p) is either PGL(2,p) or
C_{2} X PSL(2, p).

 Available as
PostScript
and as PDF

2002/6
 Colin M.
Campbell,
Peter P.
Campbell,
H. Doostie and
Edmund F.
Robertson

 On the Fibonacci length of powers of dihedral
groups.

 In this paper we examine the Fibonacci lengths of
powers of dihedral groups.

 Available as
PostScript
and as PDF

2002/5
 Colin M. Campbell,
Peter P. Campbell,
H. Doostie and
Edmund F. Robertson

 The Fibonacci length for certain metacyclic groups.

 In this paper we examine the Fibonacci length of certain groups including some due to Fox and certain Fibonacci groups.

 Available as
PostScript
and as PDF

2002/4
 Colin M. Campbell,
George Havas,
Alexander Hulpke and
Edmund F. Robertson

 The simple group L_{3}(5) is efficient

 We prove that the simple group L_{3}(5)
which has order 372000
is efficient by providing an efficient presentation for it.
This leaves one simple group with order less than one
million, S_{4}(4) which has order 979200, whose efficiency or
otherwise remains to be determined.

 Available as
gzipped PostScript
and as gzipped PDF

2002/3
 Petra E. Holmes, Stephen A.
Linton and Scott H. Murray 
 Product replacement in the monster

 We show that the product replacement algorithm can be used to
produce random elements of the Monster group.

 Available as
gzipped PostScript
and as gzipped PDF

2002/2
 Luis
Descalco and Nik Ruskuc. 
 Subsemigroups of the bicyclic monoid

 In this paper we give a description of all subsemigroups of the
bicyclic monoid B. We show that there are essentially five different
types of
subsemigroups. One of them is the degenerate case, and the
remaining four split in two groups
of two, linked by the obvious antiisomorphism of B.
Each subsemigroup is characterized by a
certain collection of parameters. We describe algorithms for
obtaining these parameters from the generating set.

 Available as
PostScript
and as PDF

2002/1
 George
Havas and Edmund F
Robertson. 
 Irreducible cyclic presentations of the trivial group


We produce families of irreducible cyclic presentations of the trivial
group. These families comprehensively answer questions about such
presentations asked by Dunwoody and by Edjvet, Hammond and Thomas.
Our theorems are purely theoretical, but their derivation is based on
practical computations. We explain how we chose the computations
and how we deduced the theorems.

 Available as:
gzipped PostScript
gzipped DVI
