Alan James Cain  ·  Curriculum Vitæ
 Address Centro de Matemática Universidade do Porto Rua do Campo Alegre, 687 4169–007 Porto Portugal Email address ajcain AT fc DOT up DOT ptReplace ‘AT’ with ‘@’ and ‘DOT’ with ‘.’ Web page www.fc.up.pt/pessoas/ajcain Date of birth 9th March 1981 Nationality British citizen Languages English (Native)French (Intermediate)Japanese (Basic: JLPT N4)Portuguese (Basic)

## Positions held

 Jul. 2009–Present Research Fellow Centro de Matemática da Universidade do PortoRua do Campo Alegre 687, 4169–007 Porto, Portugal Research summary: This position, an FCT-funded five-year personal research fellowship, made me responsible for choosing the direction of my research. So far, I have worked in several interrelated areas, both alone and with collaborators. One is hyperbolic semigroups, encompassing geometric, linguistic, and other generalizations of groups that are hyperbolic in the sense of Gromov. This has yielded results such as a polynomial-time algorithm for the word problem for hyperbolic monoids (improving on the previous-known exponential-time algorithm) and links between hyperbolicity and string-rewriting systems.\par With collaborators, I constructed finite Gröbner–Shirshov bases for Plactic algebras and proved that Plactic monoids are biautomatic, answering Zelmanov’s question.\par Another important area of my work is automatic presentations, also known as FA-presentations. In joint work, I have studied closure properties of FA-presentable algebras, and developed a powerful diagrammatic technique for working with unary FA-presentations, and applied this to classify unary FA-presentable partial orders, quasi-orders, tournaments, trees, and maps. Teaching: M431 ‘Semigroups’ Course for Master’s students, presenting an introduction to semigroup theory, including presentations, the structure theory of semigroups, free, regular, inverse, and commutative semigroups, the program of classification of finite semigroups by pseudovarieties, profinite semigroups, and the Eilenberg correspondence with varieties of rational languages. I wrote the course from scratch and produced high-quality printed lecture notes for the students, including exercises, advanced problems, and solutions.
 Sep. 2008–Jun. 2009 Research Fellow Centro de Álgebra da Universidade de LisboaAv. Prof. Gama Pinto 2, 1649–003 Lisboa, Portugal Research within the project ‘Semigroups and Languages’, funded by FCT and PIDDAC (PTDC/MAT/69514/2006). Research summary: I studied automatic Clifford semigroups and also studied (with collaborators) how automatic structures and Malcev presentations interacted with the new notion of Green index subsemigroups. Teaching: Postgraduate-level short course on automatic groups and semigroups.
 Sep. 2005–Aug. 2008 Research Fellow School of Mathematics & Statistics, University of St AndrewsSt Andrews, Fife KY16 9AJ, United Kingdom I was offered this post before the completion of my Ph.D. based on my achievements during my doctoral studies. Member of Staff Council (March 2007–August 2008). Research summary: I worked as part of a large research team on the five-year interdisciplinary project ‘Critical Mass in Computational Algebra’, funded by the EPSRC (EP/C523229/1). In particular, I researched decision problems for automatic semigroups: given an automatic structure for a semigroup, is it possible to decide certain algebraic properties of the semigroup? In some cases, I proved that no such algorithm exists (for example, cancellativity and left-cancellativity are algorithmically undecidable). I also worked in related areas such as automaton semigroups (generalizing automaton groups) and automatic presentations. With collaborators, I classified all finitely generated cancellative semigroups that admit automatic presentations. Teaching: Completely revised the course to concentrate on establishing the foundations of mathematics rigorously. Student feedback was enthusiastically supportive, with 85% overall approval. Postgraduate-level short course on computing with automatic semigroups.
 Sep. 2002–May 2005 Tutor & Computer laboratory demonstrator School of Mathematics & Statistics, University of St AndrewsSt Andrews, Fife KY16 9AJ, United Kingdom I tutored the first-year mathematics courses MT1002 and MT1003. The former course (covering both pure and applied mathematics) is a prerequisite for further mathematical study at St Andrews, and therefore it was essential to help the students achieve a thorough understanding of the concepts involved. My work as a computer laboratory demonstrator consisted of aiding students to use MAPLE to solve various problems related to their work in the first year courses MT1002 and MT1003, and marking their work. The marks a student received from this laboratory work made up 10% of his or her total mark for the course.

## Education

 Sep. 2002–Jul. 2005 Ph.D. in Mathematics University of St AndrewsSt Andrews, Fife KY16 9AJ, United Kingdom Thesis: Presentations for Subsemigroups of GroupsSupervisors: Prof. E.F. Robertson, Prof. Nik Ruškuc.Examiners: Dr M. Quick (Internal), Prof. D.F. Holt (External, Univ. of Warwick). I won a prestigious Carnegie Doctoral Scholarship to fund my Ph.D. studies. My thesis was accepted without corrections. Summary of Ph.D. research: My doctoral research spanned the boundary between mathematics, specifically algebra, and computer science, specifically the theory of algorithms. It focused on the study of combinatorial and computational properties of semigroups that can be embedded into groups. The most interesting semigroups are infinite. However, they sometimes have a finite description by means of a presentation or an automatic structure. My research studied both of these concepts and also Malcev presentations, a notion introduced in 1977 by J.-C. Spehner but neglected since then. In particular, I successfully linked the near-forgotten area of Malcev presentations with the new and active one of automatic semigroups. I then exploited this link in both directions, solving problems in the one area using the tools of the other.
 Sep. 1998–Jul. 2002 M.Sci. in Mathematics with First-class Honours University of GlasgowGlasgow G12 8QQ, United Kingdom Cunninghame Prize in Mathematics; Class prizes in Mathematics in first and second year; Class prize in Computer Science in second year. President of the Maclaurin Society, the University of Glasgow student society for mathematics and statistics.

## Membership of Professional Societies

• London Mathematical Society (Elected 2006)
• Edinburgh Mathematical Society (Elected 2003)

## Research funding

 Oct. 2002–Sep. 2005 Carnegie Doctoral Scholarship These Ph.D. scholarships are a prestigious scheme funded by the Carnegie Trust for the Universities of Scotland. They are highly competitive, with less than 10% of applications being successful. The scholarship paid my tuition fees plus a grant of approximately £10,000 per year.
 Jul. 2009–Present FCT Ciência fellowship This was a five-year fellowship scheme for individual advanced researchers to pursue research at a university in Portugal, funded by FCT (the Portuguese government agency funding scientific research). The funding covered 90% of the salary (€42,000), with the remaining 10% being paid by the host institution.
 2009–Present EPSRC Project ‘Automata, Languages, Decidability in Algebra’, EP/H011978/1 Prof. Nik Ruškuc, Dr Martyn Quick, and I wrote the application for this grant. The project was funded by the United Kingdom Engineering & Physical Sciences Research Council (EPSRC) to a value of £350,974. The original plan involved me being employed as a researcher on this project at the University of St Andrews, but I declined in favour of the FCT Ciência fellowship. I remain an active participant in the project and I make frequent research visits to St Andrews.

## Research visits

• University of St Andrews, United Kingdom
(May 2009, August 2010, May 2011, August 2011, June 2012, May 2013)
• Sultan Qaboos University, Muscat, Oman
(April 2013)
• Centro de Álgebra da Universidade de Lisboa, Portugal
(September 2010, May 2012, October 2012)

## Publications

Presentations for Subsemigroups of Groups
Ph.D. thesis, University of St Andrews, 2005.
Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness
[with E. F. Robertson & N. Ruškuc]
Mathematical Proceedings of the Cambridge Philosophical Society, 141, no. 1 (2006), pp. 57–66.
DOI: 10.1017/s0305004106009236. MR: 2238642. ZBL: 1115.20043.
Subsemigroups of groups: presentations, Malcev presentations, and automatic structures
[with E. F. Robertson & N. Ruškuc]
Journal of Group Theory, 9, no. 3 (2006), pp. 397–426.
DOI: 10.1515/jgt.2006.027. MR: 2226621. ZBL: 1151.20044.
A group-embeddable non-automatic semigroup whose universal group is automatic
Glasgow Mathematical Journal, 48, no. 2 (2006), pp. 337–342.
DOI: 10.1017/s0017089506003107. MR: 2256982. ZBL: 1108.20056.
Cancellativity is undecidable for automatic semigroups
Quarterly Journal of Mathematics, 57, no. 3 (2006), pp. 285–295.
DOI: 10.1093/qmath/hai023. MR: 2253587. ZBL: 1126.20039.
A note on “Cancellativity is undecidable for automatic semigroups”
Unpublished note, 2006.
Malcev presentations for subsemigroups of groups — a survey
In C. M. Campbell, M. Quick, E. F. Robertson, & G. C. Smith, eds, Groups St Andrews 2005 (Vol. 1), no. 339 in London Mathematical Society Lecture Note Series, pp. 256–268 (Cambridge: Cambridge University Press, 2007).
MR: 2328165.
Cancellative and Malcev presentations for finite Rees index subsemigroups and extensions
[with E. F. Robertson & N. Ruškuc]
Journal of the Australian Mathematical Society, 84, no. 1 (2008), pp. 39–61.
DOI: 10.1017/s1446788708000086. MR: 2469266. ZBL: 1156.20048.
Automatic presentations for cancellative semigroups
[with G. Oliver, N. Ruškuc & R. M. Thomas]
In C. Martín-Vide, H. Fernau, & F. Otto, eds, Language and Automata Theory and Applications: Second International Conference, Tarragona, Spain, March 13–19, 2008, no. 5196 in Lecture Notes in Computer Science, pp. 149–159 (Springer, 2008).
DOI: 10.1007/978-3-540-88282-4_15. MR: 2540320. ZBL: 1157.20332.
Malcev presentations for subsemigroups of direct products of coherent groups
Journal of Pure and Applied Algebra, 213, no. 6 (2009), pp. 977–990.
DOI: 10.1016/j.jpaa.2008.10.006. MR: 2498789. ZBL: 1178.20050.
Automaton semigroups
Theoretical Computer Science, 410, no. 47–49 (2009), pp. 5022–5038.
DOI: 10.1016/j.tcs.2009.07.054. MR: 2583696. ZBL: 1194.68133.
Automatic presentations for semigroups
[with G. Oliver, N. Ruškuc & R. M. Thomas]
Information and Computation, 207, no. 11 (2009), pp. 1156–1168.
DOI: 10.1016/j.ic.2009.02.005. MR: 2566948. ZBL: 1192.20040.
Decision problems for finitely presented and one-relation semigroups and monoids
[with V. Maltcev]
International Journal of Algebra and Computation, 19, no. 6 (2009), pp. 747–770.
DOI: 10.1142/s0218196709005366. MR: 2572873. ZBL: 1201.20055.
Monoids presented by rewriting systems and automatic structures for their submonoids
International Journal of Algebra and Computation, 19, no. 6 (2009), pp. 771–790.
DOI: 10.1142/s0218196709005317. MR: 2572874. ZBL: 1201.20054.
Automatic semigroups and Bruck–Reilly extensions
Acta Mathematica Hungarica, 126, no. 1–2 (2010), pp. 1–15.
DOI: 10.1007/s10474-009-8063-8. MR: 2593314.
Automatic presentations and semigroup constructions
[with G. Oliver, N. Ruškuc & R. M. Thomas]
Theory of Computing Systems, 47, no. 2 (2010), pp. 568–592.
DOI: 10.1007/s00224-009-9216-4. MR: 2652030. ZBL: 1204.68118.
Deus ex machina and the aesthetics of proof
Mathematical Intelligencer, 32, no. 3 (Sept. 2010), pp. 7–11.
DOI: 10.1007/s00283-010-9141-z. MR: 2721302. ZBL: 1247.00009.
An annotated translation of Yves Marie André’s Essay on Beauty (1741)
(Ebook, 2010).
Unary FA-presentable semigroups
[with N. Ruškuc & R. M. Thomas]
International Journal of Algebra and Computation, 22, no. 4 (2012).
Green index in semigroup theory: generators, presentations, and automatic structures
[with R. Gray & N. Ruškuc]
Semigroup Forum, 85, no. 3 (2012), pp. 448–476.
Context-free rewriting systems and word-hyperbolic structures with uniqueness
[with V. Maltcev]
International Journal of Algebra and Computation, 22, no. 7 (2012).
Monoids $\mathrmMon\langle a,b \mid a^\alpha b^\beta a^\gamma b^\delta a^\varepsilon b^\varphi = b\rangle$ admit finite complete rewriting systems
[with V. Maltcev]
Technical report. February 2013.
arXiv: 1302.2819.
Hyperbolicity of monoids presented by confluent monadic rewriting systems
Beiträge zur Algebra und Geometrie, 2013. Forthcoming.
Automatic structures for subsemigroups of Baumslag–Solitar semigroups
Semigroup Forum, 2013. Forthcoming.
arXiv: 1303.1112.
Finite Gröbner–Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids
[with R. Gray & A. Malheiro]
Submitted.
arXiv: 1205.4885.
Automatic Clifford semigroups
Submitted.
Markov semigroups, monoids, and groups
[with V. Maltcev]
Submitted.
arXiv: 1202.3013.
Finitely presented monoids with linear Dehn function need not have regular cross-sections
[with V. Maltcev]
Submitted.
arXiv: 1203.0473.
Subalgebras of FA-presentable algebras
[with N. Ruškuc]
Submitted.
arXiv: 1206.5548.
Monoids $\mathrmMon\langle a,b \mid a^\alpha b^\beta a^\gamma b^\delta = b\rangle$ admit finite complete rewriting systems
[with V. Maltcev]
Submitted.
arXiv: 1302.0982.
Unary FA-presentable binary relations: transitivity and classification results
[with N. Ruškuc]
Submitted.
arXiv: 1303.0214.
Decision problems for word-hyperbolic semigroups
Submitted.
arXiv: 1303.1763.
For a few elements more: A survey of finite Rees index
[with V. Maltcev]
In preparation.
Complete rewriting systems and biautomaticity for Chinese and hypoplactic monoids
[with R. Gray & A. Malheiro]
In preparation.
A countable family of congruence-free finitely presented monoids
[with F. Al-Kharousi, V. Maltcev & A. Umar]
In preparation.

## Seminars & Conference talks

‘Certain properties of subsemigroups of free groups’
Seminar: University of St Andrews, 13th August 2003.
‘Automatic semigroups & Malcev presentations I’
Informal seminar: Friday Group, University of St Andrews, 26th March 2004.
‘Automatic semigroups & Malcev presentations II’
Informal seminar: Friday Group, University of St Andrews, 7th May 2004.
‘Malcev presentations’
Seminar: University of St Andrews, 17th June 2004.
‘Malcev presentations’
Conference talk: Postgraduate Pure Mathematics in the North East 2004, University of Newcastle, 28th June 2004.
‘Malcev presentations for subsemigroups of groups’
Invited seminar: University of Glasgow, 13th October 2004.
‘A survey of Malcev presentations for subsemigroups of groups’
Conference talk: Groups St Andrews 2005, University of St Andrews, 31st July 2005.
‘Decidability and undecidability for automatic semigroups’
Invited seminar: University of Edinburgh & Heriot–Watt University (Joint), 15th November 2005.
‘An introduction to decidability for automatic semigroups’
Short course: University of St Andrews, 28th November–12th December 2005.
‘Cancellative and Malcev presentations for subsemigroups and extensions’
Conference talk: Semigroup Day ’06, Heriot–Watt University, 5th July 2006.
‘Decidability for automatic semigroups’
Conference talk: International Workshop on Computational and Algorithmic Aspects of Semigroup Theory, University of St Andrews, 6th September 2006.
‘Automatic presentations for cancellative semigroups’
Conference talk: 2nd International Conference on Language and Automata Theory and Applications, Universitat Rovira i Virgili, Tarragona, Spain, 18th March 2008.
‘Automatic presentations for semigroups’
Conference talk: 2008 British Mathematical Colloquium, University of York, 27th March 2008.
‘Automaton semigroups’
Seminar: Pure Mathematics Colloquium, University of St Andrews, 29th May 2008.
‘Automatic semigroups’
Short course: Centro de Álgebra da Universidade de Lisboa, 22nd–29th October 2008.
‘Malcev presentations for subsemigroups of groups’
Seminar: Centro de Álgebra da Universidade de Lisboa, 31st October 2008.
‘Automaton semigroups’
Invited conference talk: North Britain Semigroups and Applications Network, University of St Andrews, 16th April 2009.
‘Automatic presentations and semigroups’
Seminar: Centro de Matemática da Universidade do Porto, 25th September 2009.
‘Malcev presentations for subsemigroups of groups’
Seminar: Centro de Matemática da Universidade do Porto, 30th October 2009.
‘Computing with automatic semigroups’
Conference talk: Centro de Matemática da Universidade do Porto, 15th June 2010.
‘Automatic presentations and semigroups’
Invited seminar: Centro de Álgebra da Universidade de Lisboa, 10th September 2010.
‘Hyperbolic and word-hyperbolic semigroups’
Invited conference talk: North Britain Semigroups and Applications Network, University of St Andrews, 19th May 2010.
‘Unary FA-presentable algebraic and relational structures’
Seminar: Centro de Matemática da Universidade do Porto, 15th February 2012.
‘Hyperbolicity for semigroups’
Invited seminar: Centro de Álgebra da Universidade de Lisboa, 11th May 2012.
‘Plactic monoids, rewriting systems and biautomaticity’
Seminar: Centro de Matemática da Universidade do Porto, 26th October 2012.
‘Automatic presentations for algebraic and combinatorial structures’
Invited seminar: Centro de Matemática da Universidade de Coimbra, 20th March 2013.
‘Plactic monoids and rewriting systems’
Invited seminar: Sultan Qaboos University, 23rd April 2013.