Automatic structures for subsemigroups of Baumslag--Solitar semigroups

Abstract

This paper studies automatic structures for subsemigroups of Baumslag--Solitar semigroups (that is, semigroups presented by $<x,y\mid (y{x}^m,x^{n}y)>$, where $m$ and $n$ are natural numbers). A geometric argument (a rarity in the field of automatic semigroups) is used to show that if $m>n$, all of the finitely generated subsemigroups of this semigroup are [right-] automatic. If $m<n$, all of its finitely generated subsemigroups are left-automatic. If $m=n$, there exist finitely generated subsemigroups that are not automatic. An appendix discusses the implications of these results for the theory of Malcev presentations. (A Malcev presentation is a special type of presentation for semigroups embeddable into groups.)

arXiv comment15 pages; 8 figures