Automatic presentations for semigroups

Alan James Cain; Graham Oliver; Nik Ruskuc; Richard M. Thomas

doi:10.1016/j.ic.2009.02.005

Automatic presentations for semigroups

Alan James Cain, Graham Oliver, Nik Ruskuc, Richard M. Thomas

Research output: Contribution to journal › Article › peer-review

Abstract

This paper applies the concept of FA-presentable structures to semigroups. We give a complete classification of the finitely generated FA-presentable cancellative semigroups: namely, a finitely generated cancellative semigroup is FA-presentable if and only if it is a subsemigroup of a virtually abelian group. We prove that all finitely generated commutative semigroups are FA-presentable. We give a complete list of FA-presentable one-relation semigroups and compare the classes of FA-presentable semigroups and automatic semigroups. (C) 2009 Elsevier Inc. All rights reserved.

Original language	English
Pages (from-to)	1156-1168
Number of pages	13
Journal	Information and Computation
Volume	207
Issue number	11
Early online date	19 Mar 2009
DOIs	https://doi.org/10.1016/j.ic.2009.02.005
Publication status	Published - Nov 2009

Keywords

Automatic presentation
FA-presentable
Cancellative semigroup
Virtually abelian group
Monoids

Access to Document

10.1016/j.ic.2009.02.005

Cort apsg
This is an author version of this article. The published version (c) 2009 Elsevier Inc. is available at www.sciencedirect.com
Accepted author manuscript, 217 KB

Cite this

@article{0114c87296b14c8bb07d34e153348f5a,

title = "Automatic presentations for semigroups",

abstract = "This paper applies the concept of FA-presentable structures to semigroups. We give a complete classification of the finitely generated FA-presentable cancellative semigroups: namely, a finitely generated cancellative semigroup is FA-presentable if and only if it is a subsemigroup of a virtually abelian group. We prove that all finitely generated commutative semigroups are FA-presentable. We give a complete list of FA-presentable one-relation semigroups and compare the classes of FA-presentable semigroups and automatic semigroups. (C) 2009 Elsevier Inc. All rights reserved.",

keywords = "Automatic presentation, FA-presentable, Cancellative semigroup, Virtually abelian group, Monoids",

author = "Cain, {Alan James} and Graham Oliver and Nik Ruskuc and Thomas, {Richard M.}",

note = "Special Issue: 2nd International Conference on Language and Automata Theory and Applications (LATA 2008) ",

year = "2009",

month = nov,

doi = "10.1016/j.ic.2009.02.005",

language = "English",

volume = "207",

pages = "1156--1168",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

number = "11",

}

TY - JOUR

T1 - Automatic presentations for semigroups

AU - Cain, Alan James

AU - Oliver, Graham

AU - Ruskuc, Nik

AU - Thomas, Richard M.

N1 - Special Issue: 2nd International Conference on Language and Automata Theory and Applications (LATA 2008)

PY - 2009/11

Y1 - 2009/11

N2 - This paper applies the concept of FA-presentable structures to semigroups. We give a complete classification of the finitely generated FA-presentable cancellative semigroups: namely, a finitely generated cancellative semigroup is FA-presentable if and only if it is a subsemigroup of a virtually abelian group. We prove that all finitely generated commutative semigroups are FA-presentable. We give a complete list of FA-presentable one-relation semigroups and compare the classes of FA-presentable semigroups and automatic semigroups. (C) 2009 Elsevier Inc. All rights reserved.

AB - This paper applies the concept of FA-presentable structures to semigroups. We give a complete classification of the finitely generated FA-presentable cancellative semigroups: namely, a finitely generated cancellative semigroup is FA-presentable if and only if it is a subsemigroup of a virtually abelian group. We prove that all finitely generated commutative semigroups are FA-presentable. We give a complete list of FA-presentable one-relation semigroups and compare the classes of FA-presentable semigroups and automatic semigroups. (C) 2009 Elsevier Inc. All rights reserved.

KW - Automatic presentation

KW - FA-presentable

KW - Cancellative semigroup

KW - Virtually abelian group

KW - Monoids

UR - http://www.scopus.com/inward/record.url?scp=70349754454&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2009.02.005

DO - 10.1016/j.ic.2009.02.005

M3 - Article

SN - 0890-5401

VL - 207

SP - 1156

EP - 1168

JO - Information and Computation

JF - Information and Computation

IS - 11

ER -

Automatic presentations for semigroups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this

Automatic presentations for semigroups

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Projects

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this