Automaton semigroup constructions.

DOI10.1007/S00233-014-9632-XMaRDI QIDQ744860zbMATH OpenOpenAlexFDO

Authors Tara Brough, Alan J. Cain

Publication date 12 October 2015

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.4852

zbMATH Keywords

automaton semigroupsfinite semigroupsfree productssemigroup constructionswreath products

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Abstract: The aim of this paper is to investigate whether the class of automaton semigroups is closed under certain semigroup constructions. We prove that the free product of two automaton semigroups that contain left identities is again an automaton semigroup. We also show that the class of automaton semigroups is closed under the combined operation of 'free product followed by adjoining an identity'. We present an example of a free product of finite semigroups that we conjecture is not an automaton semigroup. Turning to wreath products, we consider two slight generalizations of the concept of an automaton semigroup, and show that a wreath product of an automaton monoid and a finite monoid arises as a generalized automaton semigroup in both senses. We also suggest a potential counterexample that would show that a wreath product of an automaton monoid and a finite monoid is not a necessarily an automaton monoid in the usual sense.

Review text

In recent years, as the authors note in the introduction, ``the notion of automaton semigroup has emerged as a natural generalization of automaton group [see \textit{A. J. Cain}, Theor. Comput. Sci. 410, No. 47-49, 5022-5038 (2009; Zbl 1194.68133); \textit{V. Maltcev}, Int. J. Algebra Comput. 19, No. 1, 79-95 (2009; Zbl 1188.20068)]. As the authors write in the abstract ``The aim of paper is to investigate whether the class of automaton semigroups is closed under certain semigroup constructions. In this paper it is proved that the free product of two automaton semigroups that contain left identities is again an automaton semigroup. The class of automaton semigroups is closed under the combined operation of ``free product followed by adjoining an identity. There are some similar results. The authors state two conjectures: 1) there exist two finite semigroups \(S\) and \(T\) such that their free product is not an automaton semigroup; 2) a wreath product of an automaton monoid and a finite monoid is not necessarily an automaton monoid.

Recommendations

• Automaton semigroups
• scientific article; zbMATH DE number 3225362
• Self-automaton semigroups.
• Automatic structures for semigroup constructions.
• CAYLEY AUTOMATON SEMIGROUPS
• scientific article; zbMATH DE number 3225363
• Computing automorphisms of semigroups.
• Automatic semigroups
• Automata groups.
• Automatic semigroups producing an automaton semigroup

Cites work

• Automata over a binary alphabet generating free groups of even rank.
• Automata, dynamical systems, and groups
• Automaton semigroups
• CAYLEY AUTOMATON SEMIGROUPS
• scientific article; zbMATH DE number 1984019 (Why is no real title available?)
• scientific article; zbMATH DE number 2156384 (Why is no real title available?)
• scientific article; zbMATH DE number 2195483 (Why is no real title available?)
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• On Burnside's problem on periodic groups
• On the Burnside problem for periodic groups
• ON THE CAYLEY SEMIGROUP OF A FINITE APERIODIC SEMIGROUP
• Self-similarity and branching in group theory.
• The finiteness problem for automaton semigroups is undecidable.

Cited in

(20)

• Automaton semigroups
• On free semigroups of automaton transformations
• An automaton group with undecidable order and Engel problems
• Automatic presentations and semigroup constructions
• Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
• On the complexity of the word problem for automaton semigroups and automaton groups
• Automatic structures for semigroup constructions.
• Automaton (semi)groups: Wang tilings and Schreier tries
• scientific article; zbMATH DE number 2123356 (Why is no real title available?)
• Amalgamated free product in terms of automata constructions
• On the orbits of automaton semigroups and groups
• Automatic semigroups vs automaton semigroups
• Automaton semigroups: new constructions results and examples of non-automaton semigroups
• scientific article; zbMATH DE number 3225362 (Why is no real title available?)
• Preserving self-similarity in free products of semigroups
• Free products of semigroups defined by automata
• Automatic semigroups producing an automaton semigroup
• The finiteness problem for automaton semigroups of extended bounded activity
• On the structure theory of partial automaton semigroups
• Computing automorphisms of semigroups.

This page was built for publication: Automaton semigroup constructions.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q744860)