Campus Event Calendar
Event Entry
What and Who
Decision Problems for Automaton Groups and Monoids of BoundedActivity
Jan Philipp Wächter
Max-Planck-Institut für Informatik - D1
AG1 Advanced Mini-Course
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Friday, 15 December 2023
13:00
30 Minutes
Warning: Date has changed!
E1 4
024
Saarbrücken
Abstract
Automaton groups are groups generated by deterministic and invertible finite-state letter-to-letter transducers (usually simply called automata in this context). The class of automaton groups is famous for the many examples of groups with exotic properties it contains (e.g. Grigorchuk’s group, Gupta-Sidki groups, the Basilica group and others).
By dropping the requirement that the generating automaton needs to be invertible, the concept naturally generalizes to automaton monoids and semigroups. Based on the structure of the cycles in the generating automaton, Sidki introduced the notion of activity, which induces a hierarchy within the class of automaton groups (this idea was also generalized to monoids by Bartholdi, Godin, Klimann and Picantin). The lowest level of this hierarchy is formed by the class of finite groups and the next level is the class of automaton groups with bounded activity (often simply called bounded automaton groups). This level already contains many of the famous automaton groups (in fact, it contains the examples mentioned above). Surprisingly, however, this level of the hierarchy somehow still seems to be “finite enough” for most algebraic decision problems to be decidable (which is not the case for general automaton groups where decision problems are usually at least suspected to be undecidable).
By dropping the requirement that the generating automaton needs to be invertible, the concept naturally generalizes to automaton monoids and semigroups. Based on the structure of the cycles in the generating automaton, Sidki introduced the notion of activity, which induces a hierarchy within the class of automaton groups (this idea was also generalized to monoids by Bartholdi, Godin, Klimann and Picantin). The lowest level of this hierarchy is formed by the class of finite groups and the next level is the class of automaton groups with bounded activity (often simply called bounded automaton groups). This level already contains many of the famous automaton groups (in fact, it contains the examples mentioned above). Surprisingly, however, this level of the hierarchy somehow still seems to be “finite enough” for most algebraic decision problems to be decidable (which is not the case for general automaton groups where decision problems are usually at least suspected to be undecidable).
In the talk, we will look at some recent results in this context with an emphasis on the membership problem for monogenic subsemigroups (which was proven to be decidable by Bühler in his Master thesis) and the finiteness problem (where we will discuss some ongoing research results on its decidability). Both of these decidability results are roughly based on constructing a finite weighted automaton computing orbit sizes. With regard to future research, the nature of this automaton promises the potential to be useful for further algebraic decision problems in this area and we will also see an outlook on this.
Contact
Stefanie Katja Harres
+49 681 9325 1002
--email hidden
Virtual Meeting Details
Zoom
897 027 2575
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
No Zoom meeting available to this talk.
Stefanie Katja Harres, 12/14/2023 13:10
Stefanie Katja Harres, 12/14/2023 13:07 -- Created document.
Stefanie Katja Harres, 12/14/2023 13:07 -- Created document.