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

Abstract

An automatic presentation of a relational structure is, informally, a representation of the elements of that structure by means of a regular language such that the relations can all be recognized by finite automata. This paper shows that a finitely generated cancellative semigroup admits an automatic presentation if and only if it is a subsemigroup of a virtually abelian group.