Skip to content

Research at St Andrews

Automatic semigroups

Research output: Contribution to journalArticle

Abstract

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.

Close

Details

Original languageEnglish
Pages (from-to)365-391
Number of pages27
JournalTheoretical Computer Science
Volume250
Issue number1-2
DOIs
Publication statusPublished - 6 Jan 2001

    Research areas

  • automatic, group, regular, semigroup, SMALL CANCELLATION THEORY, EASY MULTIPLICATIONS, SUBSEMIGROUPS

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Automatic completely-simple semigroups

    Campbell, C. M., Robertson, E. F., Ruskuc, N. & Thomas, R. M., May 2002, In : Acta Mathematica Hungarica. 95, 3, p. 201-215 15 p.

    Research output: Contribution to journalArticle

  2. Direct products of automatic semigroups

    Campbell, C. M., Robertson, E. F., Ruskuc, N. & Thomas, RM., Aug 2000, In : Journal of the Australian Mathematical Society. 69, 1, p. 19-24 6 p.

    Research output: Contribution to journalArticle

  3. Groups St Andrews 1997 in Bath Volume 1

    Campbell, C. M., Robertson, E. F., Ruskuc, N. & Smith, GC., 1999, Cambridge University Press.

    Research output: Book/ReportBook

  4. Groups St Andrews 1997 in Bath Volume 2

    Campbell, C. M., Robertson, E. F., Ruskuc, N. & Smith, GC., 1999, Cambridge University Press.

    Research output: Book/ReportBook

  5. Groups St Andrews 2017 in Birmingham

    Campbell, C. M., Parker, C. W., Quick, M., Robertson, E. F. & Roney-Dougal, C. M., Apr 2019, Cambridge University Press. 508 p. (London Mathematical Lecture Note Series 455)

    Research output: Book/ReportBook

Related by journal

  1. On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups

    Bourne, T. & Ruškuc, N., 15 Nov 2016, In : Theoretical Computer Science. 653, p. 87-96

    Research output: Contribution to journalArticle

  2. Groups synchronizing a transformation of non-uniform kernel

    Cameron, P. J., Araujo, J. & Bentz, W., 2013, In : Theoretical Computer Science. 498, p. 1-9

    Research output: Contribution to journalArticle

  3. Deciding Word Problems of Semigroups using Finite State Automata

    Neunhoeffer, M., Pfeiffer, M. & Ruskuc, N., 2011, (In preparation) In : Theoretical Computer Science.

    Research output: Contribution to journalArticle

  4. Finite complete rewriting systems for regular semigroups

    Gray, R. & Malheiro, A., 4 Mar 2011, In : Theoretical Computer Science. 412, 8-10, p. 654-661 8 p.

    Research output: Contribution to journalArticle

  5. Computation of distances for regular and context-free probabilistic languages

    Nederhof, M. J. & Satta, G., 1 May 2008, In : Theoretical Computer Science. 395, 2-3, p. 235-254 20 p.

    Research output: Contribution to journalArticle

ID: 179770

Top