CIRCA

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:

  1. 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.

 

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.

 

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

 

  1. INTAS (2000-2003).
  2. EPSRC MathFIT: “Constraint Programming, Search and Symmetry” (2001- ).
  3. NETCA – UK network in Computer Algebra: St Andrews, Bath, QMU, London, NAG Ltd, UKC (2001- ).
  4. LMS: Visit of Sinisa Crvenkovic (Novi Sad University) (August-September 2002).
  5. EPSRC: “Computational Algebra for Commodity Parallel Machines” (2002- ).
  6. LMS: Visit of Alexander Konovalov (Zaporozhye State University) (August-September 2002).
  7. EPSRC: Support for Preparation of a Proposal for a European Network of Excellence in Symbolic Computation (ENESCO).
  8. EPSRC: ” Applications of automata and languages in the theory of pattern classes of permutations” (2003-)
  9. EPSRC: ” Semigroups and monoids in GAP” (2003-)
  10. EMS: Edinburgh Mathematical Society Research Fund, Visit of George Havas (Queesnsland).
  11. 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

 

  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. Descalco, 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): Special Issue on the Integration of Automated Reasoning and Computer Algebra Systems Journal of Symbolic Computation (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.

 

2003

 

  1. Albert, M H, Atkinson, M D and Ruskuc, N: Regular closed sets of permutations, Theoret. Comput. Sci. 306(2003), no. 1-3, 85-100.
  2. Aroujo, J, Mitchell, J D and Silva, N: On embedding countable sets of endomorphisms, Algebra Universalis  50(1) (2003), 61-67.
  3. 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.
  4. 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.
  5. Campbell, C M, Havas, G, Hulpke, A and Robertson, E F: Efficient simple groups, Comm. Algebra 31 (2003), no. 10, 5191-5197.
  6. 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).
  7. 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).
  8. Cohen, S D and Huczynska, S: Primitive free quartics with specified norm and trace, Acta Arith. 109 (2003), no. 4, 359-385.
  9. 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.
  10. Elder, M J: The loop shortening property and almost convexity. Geom. Dedicata 102 (2003), 1-18.
  11. Elder, M J: Patterns theory and geodesic automatic structure for a class of groups,  Internat. J. Algebra Comput.13 (2003), no. 2, 203-230.
  12. Elder, M J, McCammond, J and Meier, J: Combinatorial conditions that imply word-hyperbolicity for 3-manifolds, Topology 42 (2003), no. 6, 1241-1259.
  13. 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.
  14. Havas, G and Robertson, E F: Irreducible cyclic presentations of the trivial group, Experimental Mathematics 12(2003), no. 4, 478-490.
  15. 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.
  16. Higgins, P M, Howie, J M and Ruskuc, N: Set products in transformation semigroups, Proc. Roy. Soc. Edinburgh, Section A 133 (2003), 1121-1135.
  17. 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.
  18. Holmes, P E, Linton, S A and Murray, S H: Product replacement in the Monster, Experiment. Math. 12 (2003), no. 1, 123-126.
  19. Huczynska, S and Cohen, S D: Primitive free cubics with specified norm and trace, Trans. Amer. Math. Soc. 355(2003), no. 8, 3099-3116
  20. 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.
  21. O’Connor J J and Robertson, E F: The life of Johann Benedict Listing, Strabismus 11 (4) (2003), 247-250.
  22. Parker, C W and Quick, M: Maximal complements in wreath products, J. Algebra 266 (2003), 320-337.
  23. Quick, M: Finitely based varieties of pointed-groups, Arch. Math. 81 (2003), 614-620.
  24. 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.
  25. Roney-Dougal, C M: Affine groups with two self-paired orbitals, Comm. Algebra 31 (2003), no. 9, 4359-4370.
  26. 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 L3(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.