See also: Research collaborators; MathSciNet author profile; Zentralblatt MATH author profile; arXiv.org preprints
There are several established methods for describing possibly infinite semigroups in a finite manner. The most well-known is that of a semigroup presentation. Following the work of Epstein et al. [Word Processing in Groups (Boston: Jones & Bartlett, 1992)] in developing the field of automatic structures for groups, Campbell et al. [Theoret. Comput. Sci. 250 (2001), no. 1–2, pp. 365–391] began the systematic study of the extension of the concept to semigroups. A third such notion is that of an automatic presentation, which originated in theoretical computer science and has only recently been applied to algebraic structures.
There are essentially two main questions regarding these structures:
My research has studied both of these questions.
Essentially no non-trivial properties of a semigroup are decidable from a presentation for that semigroup. However, various properties can be algorithmically decided from an automatic structure [See Kambites & Otto, J. Algebra 303 (2006), no. 2, pp. 789–809]. During my Ph.D. research, I established the first known undecidablility result for an algebraic property of automatic semigroups: there is no algorithm that takes as input an automatic structure for a semigroup and decides whether that semigroup is cancellative [Q. J. Math. 57 (2006), no. 3, pp. 285–295].
Malcev presentations are a special type of presentation for any semigroup embeddable into a group. They were introduced by Spehner [Semigroup Forum 14 (1977), no. 4, pp. 295–329], but are based on Malcev’s necessary and sufficient condition for the embeddability of a semigroup into a group [A.I. Malcev, Matematicheskii Sbornik 8 (1939), no. 48, pp. 331–336]. Spehner later proved that free monoids are Malcev coherent: all of their finitely generated subsemigroups admit finite Malcev presentations [J. Pure. Appl. Alg. 58 (1989), no. 3, pp. 279–287]. After Spehner’s work, the theory of Malcev presentations languished until Robertson, Ruškuc, and I revived and extended it [Math. Proc. Cambridge Philos. Soc. 141 (2006), no. 1, pp. 57–66; J. Group Theory 9 (2006), no. 3, pp. 397–426]. I published further papers on Malcev presentations myself and jointly with Robertson and Ruškuc. I am continuing my research on Malcev presentations: there are still important open questions in the field, notably whether the class of Malcev coherent groups is closed under forming finite extensions. [For a survey of the theory of Malcev presentations, see Cain, in Campbell et al., eds, Groups St Andrews 2005, vol. 1 (Cambridge: Cambridge Univ. Press, 2007), pp. 256–268.]
That the class of semigroups admitting finite presentations is closed under passing to subsemigroups and extensions of finite Rees index was proved by Ruškuc [Proc. London Math. Soc. (3) 76 (1998), no. 2, pp. 383–405]. Together with Robertson and Ruškuc, I proved the analogous results for the classes of semigroups admitting finite Malcev, cancellative, left-cancellative, and right-cancellative presentations [J. Austral. Math. Soc. 84 (2008), no. 1, pp. 39–61].
Automatic presentations ultimately stem from computer scientists’ need to extend finite model theory to infinite structures. An automatic presentation consists of a regular language representing the elements of the structure in such a way that the relations of the structure can be recognized by synchronous finite state automata. The recent systematic study of automatic presentations was begun by Khoussainov & Nerode [in Leivant, ed., Logic and Computational Complexity (Springer, 1995), pp. 367–392].
Oliver & Thomas [in Diekert & Durand, eds, STACS ’05 (Springer, 2005), pp. 693–704] proved that the finitely generated groups that admit automatic presentations are precisely the virtually abelian groups. Oliver, Ruškuc, Thomas, and I [in Martín-Vide et al., eds, LATA 2008 (Springer, 2008), pp. 149–159.] recently proved that a finitely generated cancellative semigroup that admits an automatic presentation if and only if it embeds into a virtually abelian group.
The aim, of course, is a classification of those semigroups that admit automatic presentations. At present, this goal seems distant. A useful first step would be a classification of semigroups admitting unary automatic presentation (where the language of representatives is over a one-letter alphabet).
| Colophon | © 1998–2013 A. J. Cain |
