Automaton semigroups: New constructions results and examples of non-automaton semigroups

Tara Brough, Alan J. Cain

Research output: Contribution to journalArticle

7 Citations (Scopus)
15 Downloads (Pure)

Abstract

This paper studies the class of automaton semigroups from two perspectives: closure under constructions, and examples of semigroups that are not automaton semigroups. We prove that (semigroup) free products of finite semigroups always arise as automaton semigroups, and that the class of automaton monoids is closed under forming wreath products with finite monoids. We also consider closure under certain kinds of Rees matrix constructions, strong semilattices, and small extensions. Finally, we prove that no subsemigroup of (N,+) arises as an automaton semigroup. (Previously, (N,+) itself was the unique example of a semigroup having the ‘general’ properties of automaton semigroups (such as residual finiteness, solvable word problem, etc.) but that was known not to arise as an automaton semigroup.)

Original languageEnglish
Pages (from-to)1-15
Number of pages15
JournalTheoretical Computer Science
Volume674
DOIs
Publication statusPublished - 25 Apr 2017

Keywords

  • Automaton semigroup
  • Constructions
  • Free product
  • Small extensions
  • Wreath product

Fingerprint Dive into the research topics of 'Automaton semigroups: New constructions results and examples of non-automaton semigroups'. Together they form a unique fingerprint.

Cite this