Automatic presentations for semigroups.
type: Item
instance of: scholarly article
title: Automatic presentations for semigroups.
zbMATH Open document ID: 1192.20040
author: Alan J. Cain
author: Graham Oliver
author: Richard M. Thomas
author: N. Ruškuc
published in: Information and Computation
publication date: 2009-11-27T00:00:00Z
full work available at URL: http://hdl.handle.net/10023/2147
review text: A structure \(\mathcal A=(A,R_1,\dots,R_n)\) consists of a set \(A\), called the domain of \(\mathcal A\), and there exists \(r_i\geq 1\) such that \(R_i\) is a subset of \(A^{r_i}\) (\(1\leq i\leq n\)). A structure \(\mathcal A\) has an automatic presentation over an alphabet, if it satisfies certain conditions (see Section 2). A structure that admits an automatic presentation is said to be FA-presentable. The paper under review is concerned with FA-presentable semigroups. First, the authors prove that all finitely generated commutative semigroups are FA-presentable (Theorem 6.1). Then they observe that any finitely generated subsemigroup of a semigroup admitting an automatic presentation has polynomial growth (Theorem 7.4). After that the authors consider one-relation semigroups and characterize one-relation semigroup presentations that define FA-presentable semigroups (Proposition 9.1). Later they give a complete classification of finitely generated FA-presentable cancellative semigroups and prove that a finitely generated cancellative semigroup is FA-presentable if and only if it embeds into a virtually Abelian group (Theorem 10.1). Finally, they consider the relationship between the class of FA-presentable semigroups and automatic semigroups (Proposition 11.2).
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5639681
zbMATH Keywords: finitely generated cancellative semigroups
zbMATH Keywords: finitely presented semigroups
zbMATH Keywords: automatic presentations
zbMATH Keywords: FA-presentable semigroups
zbMATH Keywords: commutative semigroups
zbMATH Keywords: automatic semigroups
reviewed by: A. Sinan Çevik
MaRDI profile type: Publication
OpenAlex ID: W2147596124
cites work: Q3859267
cites work: Finite presentations of infinite structures: Automata and interpretations
cites work: CANCELLATIVITY IS UNDECIDABLE FOR AUTOMATIC SEMIGROUPS
cites work: A GROUP-EMBEDDABLE NON-AUTOMATIC SEMIGROUP WHOSE UNIVERSAL GROUP IS AUTOMATIC
cites work: Automatic semigroups
cites work: Q3848243
cites work: Automaticity of ordinals and of homogeneous graphs
cites work: Commutative monoids have complete presentations by free (non-commutative) monoids
cites work: Word hyperbolic semigroups
cites work: ON GROUPS AND COUNTER AUTOMATA
cites work: Q4003861
cites work: A characterization of the group congruences on a semigroup
cites work: Cancellative semigroups of power growth
cites work: Q3785043
cites work: Q3350136
cites work: Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
cites work: On a subclass of context-free groups
cites work: Q4846425
cites work: Q4227129
cites work: Uniform decision problems for automatic semigroups.
cites work: Subsemigroups of nilpotent groups
cites work: Describing Groups
cites work: STACS 2005
cites work: Q3838758
cites work: Q5331568
cites work: Q5561959
cites work: Semigroups with one defining relation whose elementary theories are solvable
cites work: Q4881628
DOI: 10.1016/J.IC.2009.02.005
description: scientific article; zbMATH DE number 5639681