TY - JOUR
T1 - Automatic semigroups
AU - Campbell, Colin Matthew
AU - Robertson, Edmund Frederick
AU - Ruskuc, Nikola
AU - Thomas, RM
N1 - Foundational paper in a specialist journal
PY - 2001/1/6
Y1 - 2001/1/6
N2 - The area of automatic groups has been one in which significant advances have been made in recent years. While it is clear that the definition of an automatic group can easily be extended to that of an automatic semigroup, there does not seem to have been a systematic investigation of such structures. It is the purpose of this paper to make such a study.We show that certain results from the group-theoretic situation hold in this wider context, such as the solvability of the word problem in quadratic time, although others do not, such as finite presentability. There are also situations which arise in the general theory of semigroups which do not occur when considering groups; for example, we show that a semigroup S is automatic if and only if S with a zero adjoined is automatic, and also that S is automatic if and only if S with an identity adjoined is automatic. We use this last result to show that any finitely generated subsemigroup of a free semigroup is automatic. (C) 2001 Elsevier Science B.V. All rights reserved.
AB - The area of automatic groups has been one in which significant advances have been made in recent years. While it is clear that the definition of an automatic group can easily be extended to that of an automatic semigroup, there does not seem to have been a systematic investigation of such structures. It is the purpose of this paper to make such a study.We show that certain results from the group-theoretic situation hold in this wider context, such as the solvability of the word problem in quadratic time, although others do not, such as finite presentability. There are also situations which arise in the general theory of semigroups which do not occur when considering groups; for example, we show that a semigroup S is automatic if and only if S with a zero adjoined is automatic, and also that S is automatic if and only if S with an identity adjoined is automatic. We use this last result to show that any finitely generated subsemigroup of a free semigroup is automatic. (C) 2001 Elsevier Science B.V. All rights reserved.
KW - automatic
KW - group
KW - regular
KW - semigroup
KW - SMALL CANCELLATION THEORY
KW - EASY MULTIPLICATIONS
KW - SUBSEMIGROUPS
UR - http://www.scopus.com/inward/record.url?scp=0034899693&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(99)00151-6
DO - 10.1016/S0304-3975(99)00151-6
M3 - Article
SN - 0304-3975
VL - 250
SP - 365
EP - 391
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -