Pre-prints

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.

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.

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.

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.

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.

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.

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.

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.

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.

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₁ , Co₂ and Co₃ .

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.

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.

The group G is called n-rewritable for n > 1, if for each sequence of n elements x₁ , x₂ , . . . , x_n ∈ G there exists a non-identity permutation σ ∈ S_n such that x₁ x₂ . . . x_n = x_σ(1) x_σ(2) . . . x_σ(n). Using computers, Blyth and Robinson (1990) verified that the alternating group A₅ 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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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

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.

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 reification 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, reification 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.

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.

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=1Y_k,n.

This paper investigates t-intersecting families of injections, where two injections a, b from [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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

REPLACED BY 2008/9

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.