Automatic presentations and semigroup constructions

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

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

An automatic presentation for a relational structure is, informally, an abstract representation of the elements of that structure by means of a regular language such that the relations can all be recognized by finite automata. A structure admitting an automatic presentation is said to be FA-presentable. This paper studies the interaction of automatic presentations and certain semigroup constructions, namely: direct products, free products, finite Rees index extensions and subsemigroups, strong semilattices of semigroups, Rees matrix semigroups, Bruck-Reilly extensions, zero-direct unions, semidirect products, wreath products, ideals, and quotient semigroups. For each case, the closure of the class of FA-presentable semigroups under that construction is considered, as is the question of whether the FA-presentability of the semigroup obtained from such a construction implies the FA-presentability of the original semigroup[s]. Classifications are also given of the FA-presentable finitely generated Clifford semigroups, completely simple semigroups, and completely 0-simple semigroups.

Original languageEnglish
Pages (from-to)568-592
Number of pages25
JournalTheory of Computing Systems
Volume47
Issue number2
Early online date16 May 2009
DOIs
Publication statusPublished - Aug 2010

Keywords

  • Automatic presentation
  • FA-presentable
  • Semigroup construction
  • Clifford semigroup
  • Completely simple semigroup
  • Subsemigroups

Fingerprint

Dive into the research topics of 'Automatic presentations and semigroup constructions'. Together they form a unique fingerprint.

Cite this