# CIRCA Report 2002-2003

Introduction

CIRCA Staff

CIRCA students

Grants

Research visits

Lectures

Visitors

Conferences

Publications

## Introduction

2002 and 2003 were very active and exciting years for CIRCA. In September 2002, we moved into new accommodation on the top floor of the Mathematical Institute, bringing most of our staff and students closer together and giving us an accessible location for our library and shared computer facilities. These two years have also seen a dramatic growth in CIRCA. In 2003, we welcomed two new academic members: Ian Gent and Kevin Hammond, both from the School of Computer Science, who are involved in joint projects on *Symmetry and Search*, and *Parallel Algebraic Algorithms* (respectively). 2002 and 2003 also saw success for the Centre in publications (listed below) in attracting visitors, and in the award of EPSRC grants totalling over 700 000GBP in support of a wide range of Centre research projects. These grants, when all staff are in post (in June 2004), will bring our complement of post-doctoral researchers up to six, as well as providing funding for equipment travel and visitors. 2003 also saw the arrival of the School of Mathematics and Statistics’ new “Copson” supercomputer, providing massive computing resources for *inter alia* Centre projects.

The Centre enters 2004 larger and stronger than ever before, with more staff and students pursuing a broader range of exciting research projects and fruitful collaborations than ever before.

**Steve Linton**

Director

August 2004

## CIRCA Staff

Steve A Linton

Edmund F Robertson

Colin M Campbell

Ian Gent

Kevin Hammond

Sophie Huczynska

John J O’Connor

Martyn Quick

Nik Ruskuc

### Postdoctoral Research Fellows

Peter P Campbell

Murray J Elder

Tom Kelsey

Colva M Roney-Dougal

Leonid Timochouk

## CIRCA Students

### Ph.D.

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-)

Steve Waton (2003-)

Morteza Jafarpour (2003-)

### M.Sc.

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-)

Robert Brignall (2003-)

## Grants

### Major New Grants in 2002 and 2003:

*Computational Algebra for Commodity Parallel Machines*(2003 – 2006), EPSRC, 153 390GBP

Kevin Hammond and Steve Linton.

In this project we will explore the application of Dr Hammond’s established parallel programming tools and methodology to a range of key problems in computational algebra, targeting computation on networks of workstations, “Beowulf” style clusters and similar systems.

Leonid Timochouk is employed as Research Assistant on this project.

*Symmetry and Inference*(2003 – 2006), EPSRC, 163 911GBP

Steve Linton and Ian Gent.

In this project, a companion to our ongoing project *Constraint Programming, Search and Symmetry*, we broaden and continue our work in the use of computational group theoretic techniques to manage symmetry in constraint programming (an industrially important search technique developed in the AI community).

Colva Roney-Dougal is employed as Research Assistant on this project.

*Applications of Automata and Languages in the Theory of Pattern Classes of Permutations*(2004 – 2007), EPSRC, 157 723GBP

Nik Ruskuc, Steve Linton, Edmund Robertson, in collaboration with the University of Otago (NZ).

Pattern classes of permutations arise naturally when considering various sorting devices (such as stacks) connected in various ways. Every pattern class can also be described in terms of avoiding a collection of patterns (basis). A number of natural algorithmic and complexity questions arise: determining the enumeration sequence or its asymptotic behaviour, membership testing, determining the basis, etc. Recent advances by CIRCA members, students and visitors include new connections between pattern classes and regular languages, major progress towards a structure theory, and an in-depth analysis of antichains. In this project we want to build on these recent advances, in two major ways. Firstly, we want to implement algorithms arising from our investigations, and use them to treat a number of open problems. Secondly, we would like to develop the full potential of our theory, by extending it to languages other than regular, and to fundamental constructions such as unions, merges and wreath products. As a result of our work we hope to have a structure theory of pattern classes, unifying its Computer Science and Combinatorial aspects, a series of algorithms for dealing with pattern classes based on this theory, and a suite of implementations, available to other researchers in the area.

Murray Elder is employed as a Research Assistant on this project.

*Semigroups and Monoids in GAP*(2004 – 2007), EPSRC, 144 327GBP

Nik Ruskuc, Edmund Robertson, Steve Linton.

Semigroups and monoids are among the most fundamental mathematical objects, arising naturally as semigroups of transformations of sets or words over an alphabet, and also providing a bridge between mathematics and computer science. Therefore the availability of computational tools for these algebraic structures will influence the development of a variety of seemingly disconnected scientific disciplines, going well beyond mainstream semigroup theory. Although there is a significant body of work in this area, it is fragmented and imbalanced, with theoretical results outnumbering fully described algorithms and practical implementations. The aim of this project is to address these problems. The proposers will use their combined expertise in different areas of algebra, and experiences of their pioneering GAP package MONOID dealing with transformation monoids, to build an integrated GAP library of data structures and algorithms, bringing together all the existing major algorithms. The project will then proceed to address a second negative consequence of fragmentation: the lack of understanding of connections between different methods and algorithms. This will result in the development of a series of new, more powerful and integrated algorithms. Finally, the developed computational tools will be used to advance the understanding of a number of open problems. such as one relation semigroups. Cernv’s conjecture for reset automata etc.

James Mitchell is employed as a Research Assistant on this project.

### Complete List of Current CIRCA Grants

- INTAS (2000-2003).
- 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).
- 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).
- EPSRC: ” Applications of automata and languages in the theory of pattern classes of permutations” (2003-)
- EPSRC: ” Semigroups and monoids in GAP” (2003-)
- EMS: Edinburgh Mathematical Society Research Fund, Visit of George Havas (Queesnsland).
- EPSRC: “Symmetry and Search Network”

## Research Visits

### 2002

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.

### 2003

CMC: Galway, Ireland; RWTH Aachen, Germany

EFR: RWTH Aachen, Germany.

## Lectures

### 2002

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.

### 2003

CMC: ‘Groups Galway’, Galway, Ireland; ‘NSAC’03’, Novi Sad, Serbia.

CMRD: ‘Groups and Computation IV’, Columbus Ohio; University of Sydney; University of Warwick; University of Newcastle, ‘Nikolaus Conference’, Aachen.

SH: University of Edinburgh; ‘7th Finite Fields Symposium’, Toulouse, France; University of Exeter.

SAL: ‘Mathematics on the Semantic Web’, Eindhoven; ‘Mathematical Software for the Working Mathematician’, New York; ‘Modular Invariants and Representations of Finite Groups: Theory and Computation’, Canterbury; ‘Workshop on Symmetry and Constraint Programming’, Kinsale, Ireland; ‘Nikolaus Conference’, Aachen.

MQ: University of Newcastle; University of Cambridge.

EFR: ‘British Mathematical Colloquium’, Birmingham; University of Warwick.

NR: ‘NSAC’03’, Novi Sad, Serbia; University of Cambridge.

## Visitors

### 2002

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

### 2003

Duane M Broline (Eastern Illinois)

Leonard H Soicher (QMW)

Richard M Thomas (Leicester)

Bettina Eick (Braunschweig)

Pedro V Silva (Porto)

Michael D Atkinson (Otago)

Isabel M Araujo (Evora)

Michael H Albert (Otago)

Mohammad S Samman (King Fahd, Saudi Arabia)

Gonca Ayik (Cukurova)

Hayrullah Ayik (Cukurova)

Warwick Harvey (Imperial College)

Jan Willem Knopper (Eindhoven)

Jozsef Pelikan (Budapest)

Goetz Pfeiffer (Galway)

W Nickel (Darmstadt)

George Havas (Queensland)

James D Mitchell (Lisbon)

Duncan W Parkes (Leicester)

Lev Pliner

Imre Leader (Cambridge)

Alice C Niemeyer (Western Australia)

Gerhard Hiss (RWTH Aachen)

Nick D Gilbert (Edinburgh)

## Conferences

Instructional GAP workshop

Scottish Algebra Day

## Publications

### 2002

- Campbell, C M, Havas, G, Hulpke A and Robertson E F: The simple group
*L*_{3}(5) is efficient,*Comm. Alg.***30**(2002), 971-975. - 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. - Campbell, C M, Robertson, E F, Ruskuc, N and Thomas, R M: Automatic completely-simple semigroups,
*Acta Math. Hungar.***96**(2002), 201-215. - 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. - Campbell, C M, Havas, G, Hulpke, A and Robertson, E F: Efficient simple groups,
*Comm. Algebra***30**(2002), 4613-4619. - Descalco, L and Ruskuc, N: On automatic Rees matrix semigroups,
*Comm. Algebra***30**(2002), 1207-1226. - Hoffmann, M, Thomas, R M and Ruskuc, N: Automatic semigroups with subsemigroups of finite Rees index,
*Internat. J. Algebra Comput.***12**(2002), 463-476. - Linton, S A, Pfeiffer, G, Robertson, E F and Ruskuc, N: Computing transformation semigroups,
*J. Symbolic Comput.***33**(2002), 145-162. - Linton, S A and Sebastiani, R (Eds): Special Issue on the Integration of Automated Reasoning and Computer Algebra Systems
*Journal of Symbolic Computation*(4)**34**(October 2002). - 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.

### 2003

- Albert, M H, Atkinson, M D and Ruskuc, N: Regular closed sets of permutations,
*Theoret. Comput. Sci.***306**(2003), no. 1-3, 85-100. - Aroujo, J, Mitchell, J D and Silva, N: On embedding countable sets of endomorphisms,
*Algebra Universalis***50**(1) (2003), 61-67. - Banks, D and Linton, S A: Counting Cases in Marching Cubes: Toward a Generic Algorithm for Producing Substitopes, Best Paper at IEEE Visualization 2003, proceedings released on DVD by the IEEE, 2003.
- Campbell, C M, Campbell, P P, Hopson, B T K and Robertson, E F: On the efficiency of direct powers of
*PGL*(2,*p*), Recent advances in group theory and low-dimensional topology (Pusan, 2000), 27-34,*Res. Exp. Math.***27**, Heldermann, Lemgo, 2003. - Campbell, C M, Havas, G, Hulpke, A and Robertson, E F: Efficient simple groups,
*Comm. Algebra***31**(2003), no. 10, 5191-5197. - Campbell, C M, Robertson, E F and Smith, G C (editors),
*Groups St Andrews*2001*in Oxford*, Volume 1, London Mathematical Society**304**, Cambridge University Press, Cambridge (2003). - Campbell, C M, Robertson, E F and Smith, G C (editors),
*Groups St Andrews*2001*in Oxford*, Volume 2, London Mathematical Society 305, Cambridge University Press, Cambridge (2003). - Cohen, S D and Huczynska, S: Primitive free quartics with specified norm and trace,
*Acta Arith.***109**(2003), no. 4, 359-385. - Cohen, S D and Huczynska, S: The primitive normal basis theorem – without a computer,
*J. London Math. Soc.*(2)**67**(2003), no. 1, 41-56. - Elder, M J: The loop shortening property and almost convexity.
*Geom. Dedicata***102**(2003), 1-18. - Elder, M J: Patterns theory and geodesic automatic structure for a class of groups,
*Internat. J. Algebra Comput.***13**(2003), no. 2, 203-230. - Elder, M J, McCammond, J and Meier, J: Combinatorial conditions that imply word-hyperbolicity for 3-manifolds,
*Topology***42**(2003), no. 6, 1241-1259. - Gent, I P, Harvey, W, Kelsey, T W and Linton, S A: Generic SBDD Using Computational Group Theory, In Principles and Practice of Constraint Programming – CP 2003, volume 2833 in
*Lecture Notes in Computer Science*, pages 333-347, Springer-Verlag, 2003. - Havas, G and Robertson, E F: Irreducible cyclic presentations of the trivial group,
*Experimental Mathematics***12**(2003), no. 4, 478-490. - Higgins, P M, Howie, J M, Mitchell, J D and Ruskuc, N: Countable versus uncountable ranks in infinite semigroups of transformations and relations,
*Proc. Edinb. Math. Soc.*(2)**46**(2003), no. 3, 531-544. - Higgins, P M, Howie, J M and Ruskuc, N: Set products in transformation semigroups,
*Proc. Roy. Soc. Edinburgh*, Section A**133**(2003), 1121-1135. - Higgins, P M, Mitchell, J D and Ruskuc, N: Generating the full transformation semigroup using order preserving mappings,
*Glasg. Math. J.***45**(2003), no. 3, 557-566. - Holmes, P E, Linton, S A and Murray, S H: Product replacement in the Monster,
*Experiment. Math.***12**(2003), no. 1, 123-126. - Huczynska, S and Cohen, S D: Primitive free cubics with specified norm and trace,
*Trans. Amer. Math. Soc.***355**(2003), no. 8, 3099-3116 - Hulpke, A and Linton, S A: Total Ordering on Subgroups and Cosets, In
*Proceedings of International Symposium on Symbolic and Algebraic Computation*, 2003, pages 156 – 160, ACM Press, Philadelphia, 2003. - O’Connor J J and Robertson, E F: The life of Johann Benedict Listing,
*Strabismus***11**(4) (2003), 247-250. - Parker, C W and Quick, M: Maximal complements in wreath products,
*J. Algebra***266**(2003), 320-337. - Quick, M: Finitely based varieties of pointed-groups,
*Arch. Math.***81**(2003), 614-620. - Robertson, E F, Ruskuc, N and Thomson, M R: Finite generation and presentability of wreath products of monoids, J. Algebra 266 (2003), no. 2, 382-392.
- Roney-Dougal, C M: Affine groups with two self-paired orbitals,
*Comm. Algebra***31**(2003), no. 9, 4359-4370. - Roney-Dougal, C M and Unger, W R: The affine primitive permutation groups of degree less than 1000,
*J. Symbolic Comput.***35**(2003), no. 4, 421-439.

## CIRCA Preprints

### 2002

**2002/1**

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

Luis Descalco and Nik Ruskuc, *Subsemigroups of the bicyclic monoid.***2002/3 **

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

Colin M. Campbell, George Havas, Alexander Hulpke and Edmund F. Robertson, *The simple group L*_{3}(5)* is efficient.***2002/5**

Colin M. Campbell, Peter P. Campbell, H. Doostie and Edmund F. Robertson,* The Fibonacci length for certain metacyclic groups. ***2002/6**

Colin M. Campbell, Peter P. Campbell, H. Doostie and Edmund F. Robertson, *On the Fibonnaci length of powers of dihedral groups.* **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*).

### 2003

**2003/1 **

Ian Gent, Warwick Harvey, Tom Kelsey and Steve Linton, *Generic SBDD using GAP and ECLiPSe*.**2003/2**

Alexander Hulpke and Steve Linton, *Total ordering on subgroups and cosets*.**2003/3 **

David C. Banks and Steve Linton, *Counting Cases in Marching Cubes: Toward a Generic Algorithm for Producing Substitopes.***2003/4 **

Colin M. Campbell and Peter P. Campbell, *On the minimal length of semigroup presentations.*