16526369
Abstract Theorem Proving
Informally, abstraction can be described as the process of mapping a representation of a problem into a new representation. The aim of the paper is to propose a theory of abstraction. The generality of the framework is tested by formalizing and analyzing some work done in the past; its efficacy by giving a procedure which solves the false proof problem by avoiding the use of inconsistent abstract spaces.
12061015
Automatic Invention of Integer Sequences
We report on the application of the HR program (Colton, Bundy, & Walsh 1999) to the problem of automatically inventing integer sequences. Seventeen sequences invented by HR are interesting enough to have been accepted into the Encyclopedia of Integer Sequences (Sloane 2000) and all were supplied with interesting conjectures about their nature, also discovered by HR. By extending HR, we have enabled it to perform a two stage process of invention and investigation. This involves generating both the definition and terms of a new sequence, relating it to sequences already in the Encyclopedia and pruning the output to help identify the most surprising and interesting results.
17485829
Beyond Finite Domains: The All Different and Global Cardinality Constraints
We describe how the propagator for the ALL-DIFFERENT constraint can be generalized to prune variables whose domains are not just simple finite integer domains. We show, for example, how it can be used to propagate set, multiset and tuple variables.
2156641
Multiset Ordering Constraints
We identify a new and important global (or nonbinary) constraint which ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement a linear time algorithm for enforcing generalised arc-consistency on such a multiset ordering constraint. Experimental results show considerable promise.
5055655
The Complexity of Global Constraints
We study the computational complexity of reasoning with global constraints. We show that reasoning with such constraints is intractable in general. We then demonstrate how the same tools of computational complexity can be used in the design and analysis of specific global constraints. In particular, we illustrate how computational complexity can be used to determine when a lesser level of local consistency should be enforced, when decomposing constraints will lose pruning, and when combining constraints is tractable. We also show how the same tools can be used to study symmetry breaking, meta-constraints like the cardinality constraint, and learning nogoods.
11070611
The Constrainedness of Arc Consistency
We show that the same methodology used to study phase transition behaviour in NP-complete problems works with a polynomial problem class: establishing arc consistency. A general measure of the constrainedness of an ensemble of problems, used to locate phase transitions in random NP-complete problems, predicts the location of a phase transition in establishing arc consistency. A complexity peak for the AC3 algorithm is associated with this transition. Finite size scaling models both the scaling of this transition and the computational cost. On problems at the phase transition, this model of computational cost agrees with the theoretical worst case. As with NP-complete problems, constrainedness — and proxies for it which are cheaper to compute — can be used as a heuristic for reducing the number of checks needed to establish arc consistency in AC3. 
 
The authors are supported by EPSRC awards GR/L/24014 and GR/K/65706, and the EU award EU20603. The authors wish to thank other members of the APES research group for their help, and Gene Freuder.
15854568
Enumeration of eulerian and unicursal planar maps
Sum-free enumerative formulae are derived for several classes of rooted planar maps with no vertices of odd valency (eulerian maps) and with two vertices of odd valency (unicursal maps). As corollaries we obtain simple formulae for the numbers of unrooted eulerian and unicursal planar maps. Also, we obtain a sum-free formula for the number of rooted bi-eulerian (eulerian and bipartite) maps and some related results.
15896133
Worst-Case Analysis of Read's Chromatic Polynomial Algorithm
The worst-case time-complexity of Read's edge-addition/contraction algorithm for computing the chromatic polynomial of an n-vertex graph is shown to be O(n2B(n)), where B(n) is the nth Bell number, which grows faster than cn for any c but slower than n!. The factor n2 can be reduced to n, and the space-complexity from O(n3) to O(n2), by storing in arrays the information needed to reverse each transformation made on the graph. A graph G is assumed to be finite (with n vertices), unoriented and without loops or parallel edges. A t-colouring of G is a mapping from the vertex-set of G into the set {1,...,t} of colours so that no two adjacent vertices have the same colour. The chromatic polynomial P(G,t) of G is a function of t whose value for a given t is the number of t-colourings of G. Once the polynomial P(G,t) has been calculated, one can decide in polynomial time if G has a t-colouring for a given t by substituting t into the polynomial: G has a t-colouring if and only if P(G,t)>0. Since the problem of deciding whether G has a t-colouring is NP-hard [1, p. 392], it is unlikely that a polynomial-time algorithm will be found for computing the chromatic polynomial of a graph. The most commonly-used algorithm is the one proposed by Read [3]. It has been referenced and improved upon in several places in the literature (see, for example [5]) but its worst-case timeand spacecomplexity have never been published. We show here that the spacecomplexity is O(n3) and the time-complexity is O(n2B(n)), where B(n), the nth Bell number, grows faster than cn for any c but slower than n!, and we modify the algorithm so that it runs in O(nB(n)) time and uses O(n2) space. The following facts are shown in [3] and in other places: 1. P(G,t) is a polynomial of degree n in t. 2. If G is a tree then P(G,t)=t(t-1)n-1. 3. If G is not connected then the chromatic polynomial of G is the product of the chromatic polynomials of its connected components. 4. If G is a complete graph then P(G,t) = t(t-1)(t-2)...(t-n+1). (1) 5. If G is not a complete graph, let x and y be any two non-adjacent vertices. Let G+{x,y} be the graph obtained from G by adding the edge {x,y} to G. Let G(x=y) be the graph obtained from G by identifying the vertices x and y, where a vertex v is adjacent to the common vertex xy in G(x=y) if and only if v is adjacent to at least one of x and y in G. Then P(G,t) = P(G+{x,y},t) + P(G(x=y),t). (2) The algorithm in [3] for calculating P(G,t) is a recursive one based on (1) and (2). We give a non-recursive version (see Figure 1) for the purpose of analysing its spaceand time-complexity. Procedure PolyChrome(G: n-vertex graph; C: ARRAY[1..n] OF INTEGER); FOR i:=1 TO n DO C[i]:=0 END FOR; m:=n; H:=G; (* H is the current graph, which has m vertices *) Stack:=EMPTY; LOOP IF H has two non-adjacent vertices x and y THEN PUSH H+{x,y} onto Stack; H:=H(x=y); m:=m-1; ELSE C[m]:=C[m]+1; IF m<n THEN POP from Stack into H; m:=m+1; ELSE EXIT END IF END IF END LOOP END PolyChrome. Figure 1 A non-recursive version of Read's chromatic polynomial algorithm. We find P(G,t) from formula (3) below: P(G,t) = C[1]t + C[2]t(t-1) + ... + C[n]t(t-1)...(t-n+1). (3) We analyse the spaceand time-complexity of this algorithm under the assumption that the graph is represented by an adjacency matrix. The space-complexity is easy to analyse: at any time the stack will contain one graph with i vertices for each i from n down to m for a maximum of n graphs, each occupying O(n2) space, for a total of O(n3). To analyse the time-complexity we note that everything done to a graph H creating it, searching it for non-adjacent vertices, pushing it onto the stack and popping it off again takes O(n2) elementary operations, so that the total number of operations performed is O(n2) multiplied by the number of graphs the algorithm has to treat. The branching tree for this algorithm is a binary tree whose nodes are the graphs H the algorithm has to treat, with G as its root and the complete graphs as its leaves, and each internal node H for which the nonadjacent vertices x and y have been found has H+{x,y} and H(x=y) as its children. Each time the algorithm treats a complete graph it increases C[m] by 1 for some m, 1≤m≤n, so that the number of complete graphs it treats is C[1] + C[2] + ... + C[n], (4) and since the total number of nodes of a binary tree is twice the number of its leaves minus 1, the total time complexity of the algorithm is O(n2 multiplied by the sum in (4)). The worst case of this algorithm clearly occurs when G has no edges. In this case P(G,t)=tn. Substituting this value of P(G,t) into (3) we find that for each value of k, C[k]=S(n,k), a Stirling number of the second kind [4, p. 33]. Substituting these values into (4) we obtain the Bell number B(n). The worstcase time-complexity of this algorithm is thus O(n2B(n)). There is an asymptotic estimate for B(n) in [2]: B(n) ~ (R+1)-1/2exp[n(R+R-1-1)-1], (5)
44916266
Inversion of Cycle Index Sum Relations for 2- and 3-Connected Graphs
Abstract Algebraic inversion of cycle index sum relations is employed to derive new algorithms for counting unlabeled 2-connected graphs, homeomorphically irreducible 2-connected graphs, and 3-connected graphs. The new algorithms are significantly more efficient than earlier ones, both asymptotically and for modest values of the order. Tables of computed results are included.
3106079
Efficient Exploration With Latent Structure
When interacting with a new environment, a robot can improve its online performance by efficiently exploring the effects of its actions. The efficiency of exploration can be expanded significantly by modeling and using latent structure to generalize experiences. We provide a theoretical development of the problem of exploration with latent structure, analyze several algorithms and prove matching lower bounds. We demonstrate our algorithmic ideas on a simple robot car repeatedly traversing a path with two different surface properties.
18489826
Counting unrooted loopless planar maps
We present a formula for the number of n-edge unrooted loopless planar maps considered up to orientation-preserving isomorphism. The only sum contained in this formula is over the divisors of n.