Generators and relations for subsemigroups via boundaries in Cayley graphs

R Gray; Nik Ruskuc

doi:10.1016/j.jpaa.2011.03.017

Generators and relations for subsemigroups via boundaries in Cayley graphs

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

Abstract

Given a finitely generated semigroup S and subsemigroup T of S we define the notion of the boundary of T in S which, intuitively, describes the position of T inside the left and right Cayley graphs of S. We prove that if S is finitely generated and T has a finite boundary in S then T is finitely generated. We also prove that if S is finitely presented and T has a finite boundary in S then T is finitely presented. Several corollaries and examples are given.

Original language	English
Pages (from-to)	2761-2779
Journal	Journal of Pure and Applied Algebra
Volume	215
Issue number	11
Early online date	27 Mar 2011
DOIs	https://doi.org/10.1016/j.jpaa.2011.03.017
Publication status	Published - Nov 2011

Keywords

Semigroup
Generators
Presentations
Cayley graph
Subsemigroup
Reidemeister-Schreier rewriting

Access to Document

10.1016/j.jpaa.2011.03.017

SemigroupBoundaries10
This is an author version of this article. The definitive version (c) 2011 Elsevier B.V. is available from www.sciencedirect.com
Accepted author manuscript, 479 KB

Automata Languages Decidability: Automata, Languages, Decidability in Algebra
Ruskuc, N. (PI) & Quick, M. (CoI)
EPSRC
1/03/10 → 31/05/14
Project: Standard
Finiteness Conditions and Index: Finiteness Conditions and Index in Semigroups and Monoids
Gray, R. D. (PI)
EPSRC
1/02/08 → 31/01/11
Project: Standard
EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A. (PI), Gent, I. P. (CoI), Leonhardt, U. (CoI), Mackenzie, A. (CoI), Miguel, I. J. (CoI), Quick, M. (CoI) & Ruskuc, N. (CoI)
EPSRC
1/09/05 → 31/08/10
Project: Standard

Cite this

@article{ab2695c18bc544a79e4fa46efd512876,

title = "Generators and relations for subsemigroups via boundaries in Cayley graphs",

abstract = "Given a finitely generated semigroup S and subsemigroup T of S we define the notion of the boundary of T in S which, intuitively, describes the position of T inside the left and right Cayley graphs of S. We prove that if S is finitely generated and T has a finite boundary in S then T is finitely generated. We also prove that if S is finitely presented and T has a finite boundary in S then T is finitely presented. Several corollaries and examples are given.",

keywords = "Semigroup, Generators, Presentations, Cayley graph, Subsemigroup, Reidemeister-Schreier rewriting",

author = "R Gray and Nik Ruskuc",

year = "2011",

month = nov,

doi = "10.1016/j.jpaa.2011.03.017",

language = "English",

volume = "215",

pages = "2761--2779",

journal = "Journal of Pure and Applied Algebra",

issn = "0022-4049",

publisher = "Elsevier",

number = "11",

}

TY - JOUR

T1 - Generators and relations for subsemigroups via boundaries in Cayley graphs

AU - Gray, R

AU - Ruskuc, Nik

PY - 2011/11

Y1 - 2011/11

N2 - Given a finitely generated semigroup S and subsemigroup T of S we define the notion of the boundary of T in S which, intuitively, describes the position of T inside the left and right Cayley graphs of S. We prove that if S is finitely generated and T has a finite boundary in S then T is finitely generated. We also prove that if S is finitely presented and T has a finite boundary in S then T is finitely presented. Several corollaries and examples are given.

AB - Given a finitely generated semigroup S and subsemigroup T of S we define the notion of the boundary of T in S which, intuitively, describes the position of T inside the left and right Cayley graphs of S. We prove that if S is finitely generated and T has a finite boundary in S then T is finitely generated. We also prove that if S is finitely presented and T has a finite boundary in S then T is finitely presented. Several corollaries and examples are given.

KW - Semigroup

KW - Generators

KW - Presentations

KW - Cayley graph

KW - Subsemigroup

KW - Reidemeister-Schreier rewriting

U2 - 10.1016/j.jpaa.2011.03.017

DO - 10.1016/j.jpaa.2011.03.017

M3 - Article

SN - 0022-4049

VL - 215

SP - 2761

EP - 2779

JO - Journal of Pure and Applied Algebra

JF - Journal of Pure and Applied Algebra

IS - 11

ER -

Generators and relations for subsemigroups via boundaries in Cayley graphs

Abstract

Keywords

Access to Document

Fingerprint

Projects

Automata Languages Decidability: Automata, Languages, Decidability in Algebra

Finiteness Conditions and Index: Finiteness Conditions and Index in Semigroups and Monoids

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

Cite this