CIRCA Report 2000-2002

GAP Development Report
CIRCA students
Reseach visits

The Centre for Interdisciplinary Research in Computational Algebra was set up by the University in 2000, to support ongoing interdisciplinary research, following the split of the former School of Mathematical and Computational Sciences into the School of Mathematics and Statistics and the School of Computer Science. The Centre incorporated ongoing projects around algorithms for finitely-presented groups and semigroups, the development and maintenance of the GAP (Groups, Algorithms and Programming) system, the History of Mathematics Website and others.

These projects have continued very successfully, leading to publications, completed PhD studentships and software releases, as detailed elsewhere in this report. Additionally, the Centre has obtained funding for, and pursued successfully, initiatives such as hosting the International Symposium on Symbolic and Algebraic Computation (ISSAC) in 2000, developing the use of GAP in undergraduate teaching, providing specialized GAP development and support for researchers in Newcastle, and hosting research visitors from all over the world.

In 2002, the Centre has finally obtained our long sort central site of operations, enabling us to base most of our research students and visitors and some staff in a common area within the Mathematical Institute, and finally giving us a visible presence in the University. This has been a most successful move, and is already leading to more informal contacts and a clearer identity for the Centre as a focus for our research. We look forward to continued expansion in our new surroundings.

Steve Linton
December 2002

GAP Development Report 2000-2002

GAP development has continued throughout these two years on a widely distributed basis. Developers regularly contribute to the system from the UK, Germany, the US, the Netherlands, the Ukraine and elsewhere. Development is coordinated from St Andrews, using a wide variety of electronic tools, including mailing lists, Web sites and the CVS version control system. Occasional meetings of some or all developers “in the flesh” take place as opportunities permit.
User support is also delivered electronically, via mailing lists operated from St Andrews. We estimate that there are over 1000 sites world-wide using GAP.

GAP Releases

Version 4.2 was released in March 2000, with the following new features:

We are currently working on version 4.4, with a view to a release in spring 2003, and plan to maintain a roughly annual schedule, thereafter.

GAP Packages

As well as the “core” system, GAP now comes with a wide range of add-on packages. A flexible interface allows easy inclusion of new packages, each of which has its own documentation. New versions of packages can be released, downloaded and installed, independently of releases of GAP. In version 4.3, some feature of the core system have actually been moved into packages to allow greater flexibility in updates. A great deal of cutting-edge development now takes place in packages.
We operate a refereeing system for packages, intended both to provide quality assurance for the user, and recognition for the authors. In version 4.3, the list of packages stands as follows:

Packages that were formerly part of the system

Refereed packages

Other Packages


Steve A Linton
Edmund F Robertson
Colin M Campbell
John J O’Connor
Nik Ruskuc

CIRCA Students


Andrew Cutting (1996-2000), Todd-Coxeter methods for inverse monoids.
Robert Wainwright (1996-2001), Finding “small” matrices PQ such that PDQ = S.
Robert M Thomson (1998-2001), Finiteness conditions of wreath products of semigroups and related properties of diagonal acts.
Isabel M Araujo (1998-2001), Presentations for semigroup constructions and related computational methods.
Luís Descalço (1999-2002), Automatic semigroups: constructions and subsemigroups.
James D Mitchell (1999-2002), Extremal problems in combinatorial semigroup theory.
Max Murphy (1999-2002), Restricted permutations, antichains, atomic classes and stack sorting.
Peter P Campbell (1999-2003), Efficiency and Fibonacci length in group presentations.
Erzsi Dombi (2001-)
Nelson Silva (2001-)
Maja Waldhausen (2001-)
Catarina Carvalho (2002-)
Elizabeth Kimber (2002-)
Alan Cain (2002-)
Peter Gallagher (2002-)
Robert Gray (2002-)
Dale Sutherland (2002-)


Catarina Carvalho (2001-2002), Presentations of semigroups and inverse semigroups.
Katrin Gehles (2001-2002), Ordinary characters of finite special linear groups.
Elizabeth Kimber (2001-2002), Some cyclically presented groups.
C-H Wu (2002-)


EPSRC: “GAP Development and Support” (1996-2000) Rated alpha 5/excellent.
INTAS (2000-2003).
LMS: ISSAC 2000.
EMS: ISSAC 2000.
EPSRC MathFIT: “Constraint Programming, Search and Symmetry” (2001- ).
NETCA – UK network in Computer Algebra: St Andrews, Bath, QMU, London, NAG
Ltd, UKC (2001- ).
LMS: Visit of Sinisa Crvenkovic (Novi Sad University) (August-September 2002).
LMS: Groups St Andrews 2001.
EMS: Groups St Andrews 2001.
EPSRC: “Computational Algebra for Commodity Parallel Machines” (2002- ).
LMS: Visit of Alexander Konovalov (Zaporozhye State University) (August-September 2002).
EPSRC: Support for Preparation of a Proposal for a European Network of Excellence in Symbolic Computation (ENESCO).

Research Visits


CMC: RWTH Aachen, Germany; Galway, Ireland; Lincoln, Nebraska, USA; Pusan, Korea.
EFR: Galway, Ireland; Lincoln, Nebraska, USA; RWTH Aachen, Germany.
NR: Dunedin, New Zealand.
SAL: Queen Mary University, London; City University New York; Northeastern
University, Boston; RWTH Aachen, Germany; Birmingham


CMC: Coimbra, Portugal; Trento, Italy; RWTH Aachen, Germany.
EFR: RWTH Aachen, Germany; Oberwolfach, Germany.
NR: Leicester; Evora, Portugal; Dunedin, New Zealand.
SAL: Leicester; Oberwolfach, Germany; Birmingham; RWTH-Aachen, Germany; Sienna, Italy.


CC: Centre of Algebra, Lisbon, Portugal.
CMC: Galway, Ireland; Centre of Algebra, Lisbon, Portugal; RWTH Aachen, Germany.
ED: Porto.
MM: Cambridge; Essex.
JDBM: Essex.
EFR: Centre of Algebra, Lisbon, Portugal; RWTH Aachen, Germany.
SAL: Newcastle; Brussels; RWTH Aachen, Germany.
NS: Centre of Algebra, Lisbon, Portugal.



CMC: ‘Third International Colloquium on Words, Languages and Combinatorics’, Kyoto Sangyo University Japan; ‘Germany-Korea Mathematics Workshop on Algebra and Topology’, Pusan National University, Korea.
EFR: Automata, semigroups and groups, EPSRC Regional Meeting, Edinburgh. 
NR: ‘International Conference on Geometrical and Combinatorial Methods in Group Theory and Semigroup Theory’, Lincoln, Nebraska; ‘Third International Colloquium on Words, Languages and Combinatorics’, Kyoto, Japan; ‘Workshop on Algebraic Systems, Formal Languages and Computations’, Kyoto, Japan.


CMC: ‘Groups Galway’, Galway, Ireland.
EFR: ‘Groups Galway’, Galway, Ireland.
NR: Leicester; ‘Thematic Term on Semigroups, Algorithms and Languages’, Coimbra, Portugal.
SAL: Symmetry Breaking in the Alien Tiles Puzzle, Calculemus 2001, Sienna.


CMC: ‘Tenth International Conference on Fibonacci Numbers and Applications’, Northern Arizona Universty, Flagstaff.
LD: Workshop on Semigroups and Languages, Centre of Algebra, Lisbon, Portugal.
JDBM: Workshop on Semigroups and Languages, Centre of Algebra, Lisbon, Portugal.
EFR: ‘Groups Galway’, Galway, Ireland.
NR: Joint AMS-UMI Meeting, Pisa, Italy; Worksop on Semigroups, Automata and Formal Languages, Crema, Italy; Workshop on Semigroups and Languages, Centre of Algebra, Lisbon, Portugal.



Craig A Struble (Virginia, USA)
Derek F Holt (Warwick)
Ben Hopson (Oxford)
Eamonn A O’Brien (Auckland, New Zealand)
Friedrich Otto (Kassel, Germany)
Michael Hoffmann (Leicester)
Peter M Higgins (Essex)
Richard M Thomas (Leicester)
Robert F Morse (Evansville, USA)
Scott H Murray (Chicago, USA)
Vitor H Fernandes (Lisbon, Portugal)
Walter Ledermann


Zwelethemba Mpono (Natal, South Africa)
Friedrich Otto (Kassel, Germany)
George Havas (Queensland, Australia)
Hossein Doostie (Tehran, Iran)
Isabel M Araujo (Evora, Portugal)
Leonard H Soicher (Queen Mary)
P Elizabeth Holmes (Birmingham)
Peter M Higgins (Colchester)
S Crvenkovic (Novi Sad)
Stefan Kohl (Stuttgart, Germany)
Warwick Harvey (Imperial)


Alexander B Konovalov (Zaporozhye State University)
Anton Evseev (Oxford)
Chris J Saker (Essex)
Nick D Gilbert (Edinburgh)
P Elizabeth Holmes (Birmingham)
Richard M Thomas (Leicester)
Sarah E Rees (Newcastle)
Scott H Murray


ISSAC 2000
Calculemus 2000
Groups St Andrews 2001



  1. Araujo, I M and Ruskuc, N: On finite presentability of direct products of semigroups, Algebra Colloquium, 7(2000), 83-91.
  2. Arthur, R E and Ruskuc, N: Presentations for two extensions of the monoid of order-preserving mappings on a finite chain, Southeast Asian Bulletin of Mathematics24 (2000), 1-7.
  3. Atkinson, M D, Gilbert, N, Howie, J, Linton, S A and Robertson, E F: Computational and geometric aspects of modern algebra, Cambridge University Press, Cambridge, 2000.
  4. Ayik, H, Campbell, C M, O’Connor, J J and Ruskuc, N: On the efficiency of wreath products of groups, Proc. Groups Korea ’98 (eds.Y G Baik, D L Johnson and A C Kim. Walter de Gruyter, Berlin New York 2000), 39-51.
  5. Ayik, H, Campbell, C M, O’Connor, J J and Ruskuc, N: On the efficiency of finite simple semigroups, Turkish J. Math. 24 (2000), 129-146.
  6. Ayik, H, Campbell, C M, O’Connor, J J and Ruskuc, N: The semigroup efficiency of direct powers of groups, Proc. Internat. Conf. on Semigroups, Braga, Portugal 18-23 June 1999 (eds, Paula Smith, Emilia Giraldes and Paula Martins, World Scientific, Singapore 2000), 19-25.
  7. Ayik, H, Campbell, C M, O’Connor, J J. and Ruskuc, N: Minimal presentations and efficiency of semigroups, Semigroup Forum 60 (2000), 231-242.
  8. Campbell, C M, Robertson, E F, Ruskuc, N and Thomas, R M: Direct products of automatic semigroups, J. Austral. Math. Soc. Ser. A  69 (2000), 19-24.
  9. Crvenkovic, S, Dolinka, I and Ruskuc, N: Notes on the number of operations of finite semigroups, Acta Scientiarum Mathematicarum (Szeged)66 (2000), 23-31.
  10. Doostie, H and Campbell, C M: Fibonacci length of automorphism groups involving Tribonacci numbers, Vietnam J. Math. 28 (2000), 57-66.
  11. Ruskuc, N: On finite presentability of monoids and their Schutzenberger groups, Pacific Journal of Mathematics,195 (2000), 487-509.
  12. Ruskuc, N: Presentations for monoids, their maximal subgroups, and Schutzenberger groups, Algorithmic Problems in Groups and Semigroups (eds. J.-C. Birget et al.), Birkhauser, Boston (2000), 235-249.



  1. Araujo, I M and Ruskuc, N: Finite presentability of Bruck-Reilly extensions of groups, J. Algebra242 (2001), 20-30.
  2. Araujo, I M, Branco, M J J, Fernandes, V H, Gomes, G M S and Ruskuc, N: On generators and relations for unions of semigroups, Semigroup Forum63 (2001), 49-62.
  3. Campbell, C M, Robertson, E F, Ruskuc, N and Thomas, R M: Automatic semigroups, Theoret. Comput. Sci.250 (2001), 365-391.
  4. Crvenkovic, S, Dolinka, I and Ruskuc N: Finite semigroups with few term operations, J. Pure Appl. Algebra,157 (2001), 205-214.
  5. Crvenkovic, S, Dolinka, I and Ruskuc N: The Berman conjecture is true for finite surjective semigroups and their inflations, Semigroup Forum62 (2001), 103-114.
  6. Otto, F and Ruskuc, N: Confluent monadic string-rewriting systems and automatic structures, J. Autom. Lang. Combinat., 6 (2001), 375-388.
  7. Robertson, E F, Ruskuc, N and Thomson, M R: On diagonal acts of monoids, Bull. Austral. Math. Soc. 63 (1) (2001), 167-175.



  1. Campbell, C M, Havas, G, Hulpke A and Robertson E F: The simple group L3(5) is efficient, Comm. Alg. 30(2002), 971-975.
  2. Campbell, C M, Mitchell J D and Ruskuc, N: Comparing semigroup and monoid presentations for finite monoids, Monatshefte für Mathematik 134 (2002), 287-293.
  3. Campbell, C M, Robertson, E F, Ruskuc, N and Thomas, R M: Automatic completely-simple semigroups, Acta Math. Hungar. 96 (2002), 201-215.
  4. Campbell, C M, Mitchell J D and Ruskuc, N: On defining groups efficiently without using inverses, Math. Proc. Cambridge Philos. Soc. 133 (2002), 31-36.
  5. Campbell, C M, Havas, G, Hulpke, A and Robertson, E F: Efficient simple groups, Comm. Algebra 30 (2002), 4613-4619.
  6. Descalo, L and Ruskuc, N: On automatic Rees matrix semigroups. Comm. Algebra 30 (2002), 1207-1226.
  7. Hoffmann, M, Thomas, R M and Ruskuc, N: Automatic semigroups with subsemigroups of finite Rees index, Internat. J. Algebra Comput. 12 (2002), 463-476.
  8. Linton, S A, Pfeiffer, G, Robertson, E F and Ruskuc, N: Computing transformation semigroups, J. Symbolic Comput. 33 (2002), 145-162.
  9. Linton, S A and Sebastiani, R (Eds): Journal of Symbolic Computation, Special Issue on the Integration of Automated Reasoning and Computer Algebra Systems (4) 34 (October 2002).
  10. Robertson, E F, Ruskuc, N and Thomson, M R: On finite generation and other finiteness conditions for wreath products of semigroups, Comm. Algebra 30 (2002), 3851-3873.


CIRCA Preprints

George Havas and Edmund F Robertson, Irreducible cyclic presentations of the trivial group.
Luis Descalco and Nik Ruskuc, Subsemigroups of the bicyclic monoid.
Petra E. Holmes, Stephen A. Linton and Scott H. Murray, Product replacement in the monster.
Colin M. Campbell, George Havas, Alexander Hulpke and Edmund F. Robertson, The simple group L3(5) is efficient.
Colin M. Campbell, Peter P. Campbell, H. Doostie and Edmund F. Robertson, The Fibonacci length for certain metacyclic groups.  
Colin M. Campbell, Peter P. Campbell, H. Doostie and Edmund F. Robertson, On the Fibonnaci length of powers of dihedral groups. 
Colin M. Campbell, Peter P. Campbell, B. T. K. Hopson and Edmund F. Robertson, On the efficiency of direct powers of PGL(2,p).