‘Unary FA-presentable semigroups’
[with N. Ruškuc & R. M. Thomas]
International Journal of Algebra and Computation, 22, no. 4 (2012).
DOI: 10.1142/S0218196712500385. MR: 2946303. ZBL: 1285.03048.


Automatic presentations, also known as FA-presentations, were introduced by Khoussainov and Nerode to fulfil a need to extend finite model theory to infinite structures whilst retaining the solubility of interesting decision problems. A particular focus of research has been to attempt the classification of those structures of some species that admit automatic presentations. Whilst some successes have been obtained, this appears to be a very difficult problem in general. A restricted problem, which is also of significant interest, is to ask this question where the problem is restricted to those structures with automatic presentations over a one-letter alphabet; such structures are said to be unary FA-presentable. This paper studies unary FA-presentable semigroups.

It is proven that every unary FA-presentable structure admits an injective unary automatic presentation where the language of representatives consists of every word over a one-letter alphabet. The following results are proven: Unary FA-presentable semigroups are locally finite, but non-finitely generated unary FA-presentable semigroups may be infinite. Every unary FA-presentable semigroup satisfies some Burnside identity. In a unary FA-presentable semigroup, a $\mathcal{D}$-class cannot contain both infinitely many $\mathcal{L}$-classes and infinitely many $\mathcal{R}$-classes. The $\mathcal{H}$-classes of a unary FA-presentable semigroup are of bounded size. The class of unary FA-presentable semigroups is closed under forming the ordinal sum of two semigroups, under taking finite Rees index subsemigroups, and under certain Rees matrix constructions. A finite Rees index extensions or an arbitrary subsemigroup of a unary FA-presentable semigroup need not be FA-presentable. A classification is given of the unary FA-presentable completely simple semigroups.