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


An automatic presentation for a relational structure is, informally, an abstract representation of the elements of that structure by means of a regular language such that the relations can all be recognized by finite automata. A structure admitting an automatic presentation is said to be FA-presentable. This paper studies the interaction of automatic presentations and certain semigroup constructions, namely: direct products, free products, finite Rees index extensions and subsemigroups, strong semilattices of semigroups, Rees matrix semigroups, Bruck–Reilly extensions, zero-direct unions, semidirect products, wreath products, ideals, and quotient semigroups. For each case, the closure of the class of FA-presentable semigroups under that construction is considered, as is the question of whether the FA-presentability of the semigroup obtained from such a construction implies the FA-presentability of the original semigroup[s]. Classifications are also given of the FA-presentable finitely generated Clifford semigroups, completely simple semigroups, and completely 0-simple semigroups.