Pre-prints
2012 | 2011 | 2010 | 2009 | 2008 | 2007 | 2006 | 2005 | 2004 | 2003 | 2002
(This list is no longer updated, but is left as a useful resource)
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. Raine-Fenning, B.K. Campbell, and C. Yding Andersen | ||
Which follicles make the most anti-Müllerian hormone in humans? Evidence for an abrupt decline in AMH production at the time of follicle selection | |||
Anti-Müllerian hormone (AMH) is exclusively produced by granulosa cells (GC) of the developing pre-antral 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 (q-RTâ€“PCR) and follicular AMH production (Elisa and RIA) in relation to follicular development, 87 follicles (3-13 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 5-8 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 anti-isomorphism 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 8-element set and 38447365355811944462 on a 9-element set. | |||
Available as PDF | |||
2013/4 | Lars Kotthoff, Tom Kelsey and Martin McCaffery | ||
A framework for large-scale distributed AI search across disconnected heterogeneous infrastructures | |||
We present a framework for a large-scale 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 long-running 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? | |||
Long-term (>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 frozen-thawed ovarian tissue has been re-implanted) 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. Special-purpose 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 general-purpose 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 GAC-Schema 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 GAC-Schema (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 big-O 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 Luthar-Passi 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 anti-Müllerian hormone from conception to menopause reflects ovarian activity throughout life | |||
Anti-Müllerian hormone (AMH) is a product of growing ovarian follicles. Its concentration in blood may also reflect the non-growing 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 Data-driven 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 8-rewritability for A_{5} | |||
The group G is called n-rewritable for n > 1, if for each sequence of n elements x_{1} , x_{2} , . . . , x_{n} ∈ G there exists a non-identity 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 8-rewritable. 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 | |||
Conflict-driven 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 web-scale distributed solution of closest string problems, both purely based on AI backtrack search and also hybrid numeric-AI 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 non-growing 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 large-scale 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 non-growing follicles in human ovaries | |||
The human ovary contains a fixed number of non-growing follicles (NGF) established before birth; this number declines with increasing age culminating in the menopause at 50-51 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 3-dimensional specimens. This process is time consuming, and suffers from human mis-classification, 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 non-growing follicles (NGF) established before birth that decline with increasing age culminating in the menopause at 50-51 years. The objective of this study is to model the age-related 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 cross-validation 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 large-scale 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 high-level constraint modelling languages, similar to for-loops 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 Tand 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 group-embeddable 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 low-level 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):1973-2000, 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 well-known and well-developed 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 eHealth-NHS 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 72-element 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. Roney-Dougal | ||
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, polynomial-time 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 solver-independent 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 instance-wise compilation. We formally integrate CSE into class-wise flattening,and show when class-wise compilation is preferable to instance-wise compilation. Finally, experiments confirm our theoretical findings and demonstrate the benefits of CSE-based 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 piece-wise 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. exclusive-or) 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 solver-independent 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ös-Ko-Rado 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 ∪ ^{n-1}_{k=1}Y_{k,n}. | |||
Available as PDF | |||
2009/10 | Fiona Brunk and Sophie Huczynska | ||
Some Erdös-Ko-Rado Theorems for Injections | |||
This paper investigates t-intersecting families of injections, where two injections a, bfrom [k] to [n] t-intersect 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 1-intersecting 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 t-intersecting 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 t-intersecting 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 non-growing 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 50-51 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 age-related NGF population in the human ovary from conception to menopause. Our model matches the log-adjusted NGF population to a five-parameter 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 state-of-the-art constraint solvers; Choco, ECLiPSe, Gecode, and Minion. To assess the impact of design decisions, instances of the five problem classes n-Queens, 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 FA-presentable. 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, Bruck-Reilly extensions, zero-direct unions, semidirect products, wreath products, ideals, and quotient semigroups. For each case, the closure of the class of FA-presentable semigroups under that construction is considered, as is the question of whether the FA-presentability of the semigroup obtained from such a construction implies the FA-presentability of the original semigroup[s]. Classfications are also given of the FA-presentable finitely generated Clifford semigroups, completely simple semigroups, and completely 0-simple 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 FA-presentable structures to semigroups. We give a complete classification of the finitely generated FA-presentable cancellative semigroups: namely, a finitely generated cancellative semigroup is FA-presentable if and only if it is a subsemigroup of a virtually abelian group. We prove that all finitely generated commutative semigroups are FA-presentable. We give a complete list of FA-presentable one-relation semigroups and compare the classes of FA-presentable 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 well-studied 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. Roney-Dougal | ||
The Primitive Permutation Groups of Degree Less than 4096 | |||
In this paper we use the Classification of the Finite Simple Groups, the O’Nan-Scott 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 solver-independent 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(MAP-Kinase) and Extracellular Regulated Kinase (ERK) signaling.The aim of this study was to examine the insulin-signaling 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 two-year 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 computer-aided analysis (VOCAL), with rotation steps of 30 degrees (3D-30).
Results – For the four comparisons (inter- and intra-observer; 2D and 3D-30) we obtained intraclass coefficients of 0.97 to 0.98; and standard errors ranging from 17% to 14% (for inter-observer 2D and intra-observer 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 strongly-connected 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 anti-isomorphism, 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 computer-proof 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 | |
Non-binary 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 non-binary pure value rule. This rule is capable of pruning universal variables.Following this, two problems are modelled in non-binary QCSP: the game of Connect 4, and a variant of job-shop 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 non-binary 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 Strongly-Connected 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 strongly-connected 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 run-times over the state-of-the-art 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 anti-isomorphism, 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 five-part conjecture which was made in 1977 about a family of groups related to trivalent graphs. This family covers all 2-generator, 2-relator 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 Monte-Carlo 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 worst-case 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 constraint-based 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 Roney-Dougal | ||
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 bottom-up approach. It examines some commonly-occurring 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 well-defined 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 OpenMath-based 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_{2n-2 }. Finally, we construct an interesting H-cross-section if IP_{n }, which is reminiscent of IO_{n }, the H-cross-section 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 Luthar-Passi 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. Roney-Dougal | ||
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 sub-Groupoid forms a group, and, for this case, present an algorithm for breaking all conditional symmetries that arise at a search node. Our algorithm is polynomial-time 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 2-Groups | |||
Let K be field of characteristic 2 and let G be a finite non-abelian 2-group 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 Wallace-Kelsey 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 Next-Difference 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 GAC-schema, and in the watched-literal 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 Q-powered 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 , <ahref=”http: www.cs.st-and.ac.uk=”” ~sal=”” “=””>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, symmetry-breaking during search and symmetry-breaking 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 symmetry-related 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 NP-complete class of problems. We compare our methods with each other, and with other related symmetry-breaking 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 de-cidable. 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 NP-complete. Then we report on the application of a number of AI paradigms to the problem, namely Planning, Constraint Programming, SAT, Mixed-Integer 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 centro-polyhedral 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 ≤ n-1, x_{i+n}= ∏ ^{n}_{j=1} x_{i+j-1}, 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 centro-polyhedral 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 square-free 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 non-cyclic 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 non-trivial 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 wave-front 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 refractive-index 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 Next-Difference 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 lex-ordering, 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 double-lex – 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 search-state 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 non-isomorphic 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, Baire-n, 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 Baire-nfunctions 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 five-part 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 Roney-Dougal. | ||
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 five-part 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 torsion-free 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 torsion-free 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 non-trivial 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 context-sensitive | |||
We establish a bijection from the set of all permutations (of a given length) that avoid a pattern q and a context-sensitive language | |||
Available as PostScript and as PDF. | |||
2004/12 | Colva M. Roney-Dougal | ||
The primitive groups of degree less than 2500 | |||
In this paper we use the O’Nan–Scott 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 Postscriptand 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 Xwhich 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 order-theoretic 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 non-abelian 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. Roney-Dougal | ||
New developments in symmetry breaking in search using computational group theory | |||
Symmetry-breaking in constraint satisfaction problems (CSPs) is a well-established area of AI research which has recently developed strong interactions with symbolic computation, in the form of computational group theory. GE-trees are a new conceptual abstraction, providing low-degree 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 GE-trees 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. Roney-Dougal | ||
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 low-degree 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 worst-case asymptotic running time estimates and practical results obtained with a GAP implementation. | |||
Available as PostScript and as PDF | |||
2004/3 | Colva M. Roney-Dougal, Ian Gent, Tom Kelsey, and Steve Linton | ||
Tractable symmetry breaking using restricted search trees | |||
We present a new conceptual abstraction in symmetry breaking — the GE-tree. The construction and traversal of a GE-tree breaks all symmetries in any constraint satisfaction or similar problem. We give a polynomial-time 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. Roney-Dougal | ||
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 sub-process 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 2–6) of generating symmetries, the GAP sub-process constructs a symmetry group, performs search for dominating elements when required, and provides the ECLiPSe super-process with the information needed to restrict search. Our implementation is deterministic: all non-dominated nodes are visited during search, and each dominance check either succeeds or fails in finite time, so that only non-symmetric 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 anti-isomorphism 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 |