CIRCA

CIRCA Report 2006

Introduction
CIRCA Staff
CIRCA students
Promotions and New Appointments
Grants
Research visits
Visitors
Conferences
Publications

Introduction

Another busy year for Circa! 2006 saw a high level of activity in all aspects of our research, supported by the critical Mass project which started in 2005, as well as our other grants. This report gives details of staff movememtns, publications, conferences organised and intensive collaboration with a wide range of other institutions supported by visits in both directions. 2006 also saw the start of the major European Research Infrastructure project SCIEnce:Symbolic Computation Infrastructure for Europe, coordinated by CIRCA, which brings together developers of major symbolic computation software systems and research groups with relevant supporting expertise. The project aims to make the systems more compatible, to encourage cooperation in adopting new technologies into the systems and to support joint research into symbolic computation on the emerging technology of computational grids. Work on this project at St Andrews will start in 2007, with the appointment of Alexander Konovalov.

Steve Linton
Director
April 2007

CIRCA Staff

Steve Linton
Colin M Campbell
Ian Gent
Kevin Hammond
Sophie Huczynska
Delaram Kahrobaei
Ian Miguel
James Mitchell
John J O’Connor
Martyn Quick
Edmund F Robertson
Colva Roney-Dougal
Nik Ruškuc

Senior Research Fellows

Beth Holmes
Tom Kelsey

Research Fellows

Alan Cain
Peter P Campbell
Leonid Timochouk
Vince Vatter

Support

John McDermott
Angela Miguel

CIRCA Students

Ph.D.

Morteza Jafarpour (2003-)
Peter Nightingald (2003-2007)
Steve Waton (2003-2006)
Björn Aßmann (2004-)
Robert Brignall (2004-)
Fiona Brunk (2005-)
Abram Connelly (2005-)
Yann Péresse(2005-)
Andrea Rendl (2006-2009)
Andy Grayland(2006-2010)

Promotions & New Appointments

Research Fellow
Karen Petrie
Alexander Konovalov

Support
Lynn Hynd

Departures

Delaram Kahrobaei – to a teaching post at City College of Technology at City University New York
Peter Campbell – to train as a school teacher
Leonid Timochouk – at the end of his grant
Angie Miguel – on maternity leave from 12/12/06 to 4/10/07 – Angie gave birth to Lucy Charlotte Miguel on Thursday 25th January, at 7:53am, weighing 7 pounds and 2 ounces.
Dale Sutherland – to work for Royal Canadian Mounted Police
Murray J Elder – to a teaching post at Stevens Institute of Technology, New Jersey
Chris Jefferson – to a research post at University of Oxford
Karen Petrie – to a research administration post at University of Oxford

Grants

Major New Grants in 2006:

  1. EC:SCIEnce:Symbolic Computation Infrastructure for Europe. Linton, S. Hammond K. started in 2006.

  2. EPSRC: Watched Literals and Learning for Constraint Programming Ian P. Gent was awarded in 2006.

 

Complete List of Current CIRCA Grants

  1. EC: SCIEnce: Symbolic Computation Infrastructure for Europe. Linton, S. Hammond, K. (2006-2011)
  2. EPSRC: Multidisciplinary Critical Mass in Computational Algebra and Applications. Linton, SA, Gent, IP, Miguel, I, Ruskuc, N, Quick, M, Robertson, E, Mackenzie, A, Leonhardt, U. (2005-2010)
  3. EPSRC/Royal Academy of Engineering: An Automated Constraint Modelling Assistant. Miguel, I. Research Fellowship. (2004-2009)
  4. Royal Society Dorothy Hodgkin Fellowship. Huczynska, S. (2004-2008)
  5. Royal Society Dorothy Hodgkin Fellowship. Holmes, P.E. (2003-2007)
  6. EPSRC: Applications of Automata and Languages in the Theory of Pattern Classes of Permutations. Ruskuc, N, Linton, SA, Robertson, EF. (2004-2007)
  7. EPSRC: Refinement-Driven Transformation for Effective Automated Constraint Modelling. Miguel, I. & Gent, IP. (2006-2009)
  8. EPSRC: Semigroups and Monoids in GAP. Ruskuc, N, Linton, SA, Robertson, EF. (2004-2006)
  9. EPSRC: Symmetry and Search Network. Linton, SA, Smith, BM, Melham, TF, Gent, IP, Fox, M, Kelsey, TW. (2004-2007)
  10. EPSRC: Symmetry and Inference, Linton, SA, and Gent, IP. (2003-2006)
  11. EPSRC: Computational Algebra for Commodity Parallel Machines, Hammond, K, Linton, SA. (2003-2006)
  12. EPSRC/Microsoft: CASE for New Academics Grant, Miguel, I. (2006-2009)
  13. EPSRC: Academic Fellowship. Mitchell, J. (2005-2010)


Research Visits

Robert Brignall:University of Otago, Dundedin, New Zealand
Dlearam Kahrobaei:Institute for Studies Theoretical Physics and Mathematics, Tehran, Iran; University of Geneva; University of Nottingham
Björn Aßmann: Oxford; Oberwolfach in Germany
Colva Roney-Dougal;University of Warwick Algebra Seminar, Ohio State University, Mathematics Forschunginstitut, Oberwolfach in Germany; University of Sydney
Karen Petrie: London, London Hoppers Meeting, Oxford
Chris Jefferson: Oxford; Nantes, France
Steve Linton: UWA, Perth, Australia; Mathematisches Forschunginstitut Oberwolfach in Germany; University of Birmingham; Vrije Universiteit Brussel, Belgium
Martyn Quick: Edinburgh Universities Algebra Seminar, Groups Galway 2006
James Mitchell: Centre of Algebra, University of Lisbon; Technical University of Wroclaw, Poland
Ian Miguel:University of New South Wales, Sydney;University of Melbourne; University of York; Microsoft, Cambridge
Tom Kelsey QMUL/Imperial College London, Montevideo; Glasgow University
Ian P. Gent; University of Birmingham; Nantes, France

Visitors

Akos Seress (University of Ohio)
Alan Frisch (University of York)
Alastair Stewart (University of Zimbabwe)
Andreas Distler (TU Braunschweig, Germany)
Barbera Smith (Cork Constraint Computational Centre – 4C, Ireland)
Bernadette Martinez-Hernandez (University of York)
Bilal Khan (University of New York)
Bob Gray (University Leeds)
Catarina Carvalho (University of Durham)
Chris Beck (University of Toronto)
Chris Jefferson (University of Oxford, Columbia, Canada)
Etienne Ghys (ENS de Lyon)
George Havas (University of Queensland)
Goulnara Arzhantseva (University of Geneva)
Gracinda Gomes (University of Lisbon)
Habtay Ghebrewold Asmara (University, Eritrea)
Julian West Malaspina (University-College, Nanaimo)
Karen Petrie (University of Oxford)
Luke Anthony Woodward (University of Oxford)
Mark Kambites (University of Manchester)
Mark Stather (University of Warwick)
Max Neunhoeffor (Lehrstuhl D fur Mathematik, RWTH Aachen)
Michal Morayne (University of Wroclaw, Poland)
Patrick Prosser (University of Glasgow)
Rick Thomas (University of Leicester)
Scott Murray (T U Eindhoven, The Netherlands)
Stephen Glasby (Central Washington University, USA)

Conferences Organised

Computational and Algorithmic Aspects of Semigroup Theory

This was an international workshop, was held at University of St Andrews from Tuesday 5th September to Saturday 9th September 2006. The topics included were: transformation semigroups, presentations, rewriting systems, decision problems, automatic structures, the GAP system, and complexity. The speakers were:

Fred Otto (Universitat Kassel, Germany) String-rewriting techniques for monoid-presentations;
Goetz Pfeiffer (NUI, Galway, Ireland) Algorithms for finite monoids actions on partial orders ,Applications to finite Coxeter groups;
Jean-Eric Pin (LIAFA, CNRS, and Paris VII, France) Algorithmic aspects of finite semigroup theory;
Misha Volkov (Ekatrinburg, Russia) Interpreting graphs in 0-simple semigroups with involution with applications to computational complexity and the finite basis problem.

Scottish Algebra Day (2006)

was held in University of St Andrews on Friday the 28th of April. The speakers were:

Raphael Rouquier (University of Leeds): Representations of rational Cherednik algebras.
Wolfgang Soergel (Albert-Ludwigs University, Freiburg): Special bimodules, hard Lefschetz and Andersen-Jantzen filtration.
Rob Wilson (Queen Mary, University of London): Octonions, exceptional Jordan algebras, and Ree groups.
Claas Roever (National University of Ireland, Galway): Abstract commensurators.

Publications

  1. Nik Ruškuc, A.J. Cain and E.F. Robertson, Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness, Math. Proc. Cambridge Philos. Soc. 141 (2006), 57-66.
  2. Nik Rušskuc, A.J. Cain and E.F. Robertson, Subsemigroups of groups: presentations, Malcev presentations, and automatic structures, J. Group Theory 9 (2006), 397-426.
  3. Nik Ruškuc, P.M. Higgins, J.D. Mitchell and M. Morayne, On rank properties of endomorphisms of countably infinite partially ordered sets, Bull. London Math. Soc. 38 (2006), 177-191.
  4. Miguel, S. Prestwich. Proceedings of the Fifth International Workshop on Constraint Modelling and Reformulation, Nantes, France, 2006.
  5. K.N. Brown, I. Miguel. Uncertainty and Change. in F. Rossi, P. van Beek, T. Walsh (eds), The Handbook of Constraint Programming, 2006.
  6. A.M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, T. Walsh. Propagation Algorithms for Lexicographic Ordering Constraints. Artificial Intelligence 170(10), 803-834, 2006.
  7. Colin Campbell, P. P. Campbell The Fibonacci lengths of binary polyhedral groups and related groups, Applications of Fibonacci Numbers 10 , Kluwer, (Dordrecht, 2006), 83-91.
  8. Martyn Quick, “Probabilistic generation of wreath products of non-abelian finite simple groups, II,” Internat. J. Algebra Comput. 16 (2006), no. 3, 493-503.
  9. S. Huczynska and V. Vatter “Grid classes and the Fibonacci dicotomy for restricted permutations”, The Electronic Journal of Combinatorics 13 (2006), no.1.
  10. S.Huczynska and G.L.Mullen “Frequency permutation arrays”, Journal of Combinatorial Designs 14 (2006), 463–478.
  11. V. Vatter, Bruce Sagan The Möbius function of a composition poset  Journal of Algebraic Combinatorics, 24 (006), 117.136.
  12. V. Vatter Finitely labeled generating trees and restricted permutations Journal of Symbolic Computation, 41(2006), 559.572.
  13. V. Vatter, Bruce Sagan Maximal and maximum independent sets in graphs with at most r cycles  Journal of Graph Theory, 53 (2006), 283.314.
  14. V.Vatter, Goh Chee Ying, Koh Khee Meng, and Bruce Sagan Maximal independent sets in graphs with at most r cycles Journal of Graph Theory, 53 (2006), 270.282.
  15. Brignall, R., Wreath products of permutation classes.
  16. Brignall, R., Ruškuc, N., and Vatter, V., Simple permutations: decidability and unavoidable substructures.
  17. A.M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, T. Walsh. Propagation Algorithms for Lexicographic Ordering Constraints. Artificial Intelligence 170(10), 803-834, 2006.
  18. C. Jefferson, A. Miguel, I. Miguel, A. Tarim. Modelling and Solving English Peg Solitaire. Computers and Operations Research 33(10), pages 2935-2959, 2006.
  19. J. Charnley, S. Colton, I. Miguel. Automatic Generation of Implied Constraints. Proceedings of the Seventeenth European Conference on Artificial Intelligence, 73-77, 2006.
  20. I.P. Gent, C. Jefferson, I. Miguel. Minion: A Fast, Scalable Constraint Solver. Proceedings of the Seventeenth European Conference on Artificial Intelligence, 98-102, 2006. This was judged by the chairs to be one of the ten best papers submitted to the conference. Click for more information on the Minion Constraint Solver.
  21. I.P. Gent, C. Jefferson, I. Miguel. Watched Literals for Constraint Propagation in Minion. Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming, 182-197, 2006.
  22. Karen Petrie, Tom Kelsey, Steve Linton, Chris Jefferson GAPlex Generalised Static Symmetry Breaking Proceedings of the Sixth International Workshop on Symmetry in Constraint Satisfaction Problems 2006

    Popularisation

    “In Our time” Melvyn Bragg BBC Radio 4 show on Indian Mathematics, December – Colva Roney-Dougal
    “The Power of Groups” Plus Magazine, June – Colva Roney-Dougal
    “In our Time” Melvyn Bragg BBC Radio 4 Show on Negative Numbers, March – Colva Roney-Dougal

    CIRCA Preprints

    2006/1
    Goulnara Arzhantseva, Pierre de la Harpe and Delaram Kahrobaei. The true prosoluble completion of a group: examples and open problems
    2006/2
    Chris Jefferson, Tom Kelsey, Steve Linton and Karen Petrie. GAPLex: Combining Static and Dynamic Symmetry Breaking
    2006/3
    Ian Gent, Ian Miguel, and Peter Nightingale Data Structures for Generalised Arc Consistency for Extensional Constraints
    2006/4
    Ulf Leonhardt Optical Conformity Mapping
    2006/5
    Ulf Leonhardt Notes on Conformal Invisibility Devices
    2006/6
    J. D. Bradley and P. E. Holmes Improved Bounds for the spread of sporadic groups
    2006/7
    Petra E. Holmes and Attila Mavóti Covering and generating sporadic groups 
    2006/8
    John R. Britnell, Anton Evseev, Robert M. Guralnick, Petra E. Holmes and AttilaMavótiSets of elements that pairwise generate a linear groupp
    2006/9
    Elizabeth H. Kimber, John J. O’Connor and Edmund F Robertson Cyclic Minimal Generating Sets for Abelian Groups
    2006/10
    Colin M. Campbell, George Havas and Edmund F Robertson Addendum to An Elementary Introduction to Coset Table Methods in Computational Group Theory
    2006/11
    C.M. Campbell and P.P. Campbell Search techniques, Fibonacci lengths and centro-polyhedral groups
    2006/12
    Colin M. Campbell, George Havas, Colin Ramsay and Edmund F. Robertson On the efficiency of the simple groups with order less than a million and their covers
    2006/13
    Ian P. Gent, Chris Jefferson, Tom Kelsey, Inês Lynce, Ian Miguel, Peter Nightingale, Barbara M. Smith, and S. Armagan Tarim Search in the Patience Game ‘Black Hole’
    2006/14
    Björn Aßmann, and Bettina Eick Testing polycyclicity of finitely generated rational matrix groups
    2006/15
    Chris Jefferson, Tom Kelsey, Steve Linton and Karen Petrie GAPLex: Generalised Static Symmetry Breaking
    2006/16
    Ian P. Gent, Warwick Harvey, Tom Kelsey, Groups and Constraints:Symmetry Breaking During Search and Symmetry Breaking by Dominance Detection
    2006/17
    Björn Aßmann and Steve Linton Using the Mal’cev correspondence for collection in polycyclic groups
    2006/18
    Ian P. Gent , Chris Jefferson, Ian Miguel, and Peter Nightingale Data Structures for Generalised Arc Consistency for Extensional Constraints